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


void citire (){
	
	f>>N>>M;
	for(int i=1;i<=M;i++){
		f>>x>>y>>d;
		A[x][y]=d;
	}
}
int main(){
	citire();
	for(i=2;i<=N;i++)
		if(A[1][i]!=0)
			D[i]=A[1][i];
		else
			D[i]=9999999;
	
	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(j=1;j<=N;j++)
			if(S[j]==0&&A[poz][j]!=0)
				if(D[j]>D[poz]+A[poz][j])
					D[j]=D[poz]+A[poz][j];
	
				

		
	}

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