#include<fstream>
using namespace std;
int x,y,d,D[50005],S[50005],i,j,N,M,poz,Min,k;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct nod{
	int inf,dist;
	nod* adr;
}*A[50005],*p;
void citire (){
	
	f>>N>>M;
	for(int i=1;i<=M;i++){
		f>>x>>y>>d;
		p=new nod;
		p->inf =y;
		p->dist=d;
		p->adr=A[x];
		A[x]=p;
	}
}
int main(){
	citire();
	for(i=2;i<=N;i++)
		D[i]=999999999;
	
	for(p=A[1];p;p=p->adr)
			D[p->inf]=p->dist;
	
	S[1]=1;
	
	for(i=1;i<=N;i++)
		
	{		
		Min = 9999999;
		for(j=1;j<=N;j++)
			if(S[j]==0)
				if(D[j]<Min )
				{
					Min=D[j];
					poz=j;
				}
		S[poz]=1;
		for(p=A[poz];p;p=p->adr)
			if(!S[p->inf])
				{
					
					if(D[p->inf]>D[poz]+p->dist)
					{
						D[p->inf]=D[poz]+p->dist;
						
					}
			}
	}

		for(i=2;i<=N;i++)
			if(D[i]!=999999999)
				g<<D[i]<<" ";
			else
				g<<0<<" ";
return 0;
}