#include<stdio.h>
#include<vector>

#define maxn 50005
#define pb push_back
#define mp make_pair

using namespace std;

FILE*f=fopen("dijkstra.in","r");
FILE*g=fopen("dijkstra.out","w");

int n,m,L;
int D[maxn],H[maxn],Poz[maxn];
const int INF = 1<<29;
vector< pair<int,short int> >G[maxn];

inline void urca ( int poz ){
	
	while ( poz > 1 && D[H[poz>>1]] > D[H[poz]] ){
		swap(H[poz>>1],H[poz]);
		swap(Poz[H[poz>>1]],Poz[H[poz]]);
		poz >>= 1;
	}
}

inline void coboara ( int x ){
	int y = 0;
	
	while ( x != y ){
		y = x;
		if ( 2*y <= L && D[H[2*y]] < D[H[x]] ){
			x = 2*y;
		}
		if ( 2*y+1 <= L && D[H[2*y+1]] < D[H[x]] ){
			x = 2*y+1;
		}
		
		swap(H[x],H[y]);
		swap(Poz[H[x]],Poz[H[y]]);
	}
}

inline void insert ( int nod ){
	
	H[++L] = nod; Poz[nod] = L;
	urca(L);
}

inline int pop () {
	int nod = H[1];
	
	swap(H[1],H[L]); swap(Poz[H[1]],Poz[H[L]]);
	Poz[H[L]] = 0; H[L] = 0; --L;
	coboara(1);
	
	return nod;
}

int main () {
	
	fscanf(f,"%d %d",&n,&m);
	
	for ( int i = 1 ; i <= m ; ++i ){
		int x,y,c;
		fscanf(f,"%d %d %d",&x,&y,&c);
		G[x].pb(mp(y,c));
	}
	
	for ( int i = 2 ; i <= n ; ++i ){
		D[i] = INF;
	}
	insert(1);
	
	while ( L ){
		int nod = pop();
		
		for ( vector< pair<int,short int> >::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
			int nodvcn = itt->first; int cost = itt->second;
			
			if ( D[nodvcn] > D[nod] + cost ){
				D[nodvcn] = D[nod] + cost;
				if ( Poz[nodvcn] ){
					urca(Poz[nodvcn]);
				}
				else{
					insert(nodvcn);
				}
			}
		}
	}
	
	for ( int i = 2 ; i <= n ; ++i ){
		if ( D[i] != INF )
			fprintf(g,"%d ",D[i]);
		else
			fprintf(g,"%d ",0);
	}
	fprintf(g,"\n");
	
	fclose(f);
	fclose(g);
	
	return 0;
}