#include<fstream>

#define NMAX 50002
#define inf 400000007
using namespace std;
int n,m,D[NMAX],S[NMAX],T[NMAX],poz,i,j,minu,A[1002][1002];
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int  main (){
	f>>n>>m;
	int x,y,c;
	for(i=1;i<=n;i++){
		f>>x>>y>>c;
		A[x][y]=c;
		if(x==1)
			D[y]=c;
	}
	for(i=1;i<=n;i++){
		
		for(j=1;j<=n;j++)
			if(!A[i][j])
				A[i][j]=inf;
		
		A[i][i]=0;
	}
	
	S[1]=1;

	for(i=2;i<=n;i++){
		
		if(!D[i])
			D[i]=inf;
		S[i]=0;
		
	}
	for(j=1;j<n;j++){
		minu=100000;
		for(i=1;i<=n;i++){
			if(!S[i]){
				if(D[i]<minu){
					minu=D[i];
					poz=i;
				}
			}
		}
		S[poz]=1;
		for(i=1;i<=n;i++){
			
			if(!S[i]){
				if(D[i]>D[poz]+A[poz][i])
					D[i]=D[poz]+A[poz][i];
				
			}
			
		}
		
	}
	
	for(i=2;i<=n;i++)
		g<<D[i]<<" ";
	return 0;
}