#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
#include <set>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n,i,j,m,a,b,c,cst[50005],fi,sc,x,fr[50005];
vector<pair<int,int>> vec[50005];
set<pair<int,int>> ss;

int main() {
	
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>a>>b>>c;
		vec[a].push_back(make_pair(b,c));
	}
	m=n;
	for(i=1;i<=n;i++)	cst[i]=-1;
	
	ss.insert(make_pair(0,1));
	cst[1]=0;
	bool ciclu=0;
	while(!ss.empty()&&ciclu==0)
	{
		c=(*ss.begin()).first;
		n=(*ss.begin()).second;
		ss.erase(ss.begin());
		
		for(i=0;i<vec[n].size();i++)
		{
			fi=vec[n][i].first;
			sc=vec[n][i].second;
			x=c+sc;
			if(fr[fi]>=m)	ciclu=1;
			if(x<cst[fi]||fr[fi]==0)
			{
				fr[fi]++;
				cst[fi]=x;
				ss.insert(make_pair(x,fi));
			}
		}
	}
	for(i=2;i<=m;i++)
	{
		if(cst[i]==-1)	fout<<0<<" ";
		else	fout<<cst[i]<<" ";
	}
}