#include<fstream>
#include<vector>
#define INF 1 << 25
#define maxN 50005
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int N,M,i,x,y,D[maxN],Poz[maxN],Sol[maxN];
int L,H[maxN];

struct mch{
	int nod;
	int cst;
}aux;

vector<mch>A[maxN];

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

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

void addheap(int x){
	H[++L] = x;
	Poz[x] = L;
	urca(L);
}

int extrage(int poz){
	Sol[H[poz]] = D[H[poz]];
	
	int nod = H[poz];
	int vcn;
	
	for ( int j = 0 ; j < A[nod].size() ; ++j ){
		vcn = A[nod][j].nod;
		if ( D[vcn] > D[nod] + A[nod][j].cst ){
			D[vcn] = D[nod] + A[nod][j].cst;
		}
	}
	
	swap(H[poz],H[L]);
	swap(Poz[H[poz]],Poz[H[L]]);
	--L;
	coboara(1);
	
	Poz[nod] = 0;
	D[nod] = -1;
	
	return nod;
}

int main () {
	f >> N >> M;
	for ( i = 1 ; i <= M ; ++i ){
		f >> x >> aux.nod >> aux.cst;
		A[x].push_back(aux);
	}
	
	for ( i = 2 ; i <= N ; ++i )
		D[i] = INF;
	
	H[++L] = 1;
	Poz[1] = L;
	
	extrage(1);
	
	for ( i = 2 ; i <= N ; ++i ){
		addheap(i);
	}
	
	for ( i = 1 ; i < N ; ++i ){
		int nd = extrage(1);
		
		for ( int j = 0 ; j < A[nd].size() ; ++j ){
			if ( Poz[A[nd][j].nod] )
				urca( Poz[A[nd][j].nod] );
		}
	}
	
	for ( i = 2 ; i <= N ; ++i ){
		if ( Sol[i] == INF )
			g << "0 ";
		else
			g << Sol[i] << " ";
	}
	
	f.close();
	g.close();
	
	return 0;
}