#include<fstream>
#include<vector>
#include<set>
#include<cstring>
#define  MAXN 50005
#define INF 1000000000
#define pb push_back
#define mp make_pair
using namespace std;
int N,M,x,dist,d[MAXN];
vector<int> G[MAXN],C[MAXN];
set< pair<int,int> > T;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int main() {
	int i,a,b,c;
	cin>>N>>M;
	for(i=1;i<=M;i++) 
			cin>>a>>b>>c , G[a].pb(b) , C[a].pb(c);
	for(i=1;i<=N;i++)
	            d[i]=INF;		
	T.insert(mp(0,1));
	while( T.size() ){
		   	dist=(*T.begin()).first; x=(*T.begin()).second;
			T.erase(*T.begin());
			for(i=0;i<G[x].size();i++)
			  if(d[G[x][i]]>dist+C[x][i])
			    d[G[x][i]]=dist+C[x][i],T.insert(mp(d[G[x][i]],G[x][i]));
				  			  
	  } //end while
	for(i=2;i<=N;i++)
	    if(d[i]==INF) cout<<0<<" ";
		else cout<<d[i]<<" ";
return 0;
}