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

#define maxn 50005
#define inf (1<<29)

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];
vector< pair<int,int> >G[maxn];

inline void citire () {
	
	fscanf(f,"%d %d",&n,&m);
	int x,y,c;
	for ( int i = 1 ; i <= m ; ++i ){
		fscanf(f,"%d %d %d",&x,&y,&c);
		G[x].push_back(make_pair(y,c));
	}
}

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

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

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

inline int scoate () {
	
	int nod = H[1];
	swap(poz[H[1]],poz[H[L]]);
	swap(H[1],H[L]);
	--L;
	coboara(1);
	
	return nod;
}

inline void dijkstra () {
	
	for ( int i = 2 ; i <= n ; ++i ){
		D[i] = inf;
	}
	
	insert(1);
	while ( L ){
		int nod = scoate();
		
		for ( vector< pair<int,int> >::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
			int vecin = itt->first,cost = itt->second;
			
			if ( D[vecin] > D[nod]+cost ){
				D[vecin] = D[nod]+cost;
				
				if ( poz[vecin] ){
					urca(poz[vecin]);
				}
				else{
					insert(vecin);
				}
			}
		}
	}
	
	for ( int i = 2 ; i <= n ; ++i ){
		if ( D[i] == inf )	D[i] = 0;
		fprintf(g,"%d ",D[i]);
	}
	fprintf(g,"\n");
}

int main () {
	
	citire();
	dijkstra();
	
	fclose(f);
	fclose(g);
	
	return 0;
}