#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];
int L,H[maxN];

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

vector<mch>A[maxN];

void urca(int poz){
	while ( poz != 0 && 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 = 0;
	
	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 delete_heap(){
	H[1] = H[L--]; Poz[H[1]] = 1;
	coboara(1);
}

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;
	
	++L;
	H[1] = 1; Poz[H[1]] = 1;
	
	while ( L ){
		int nod = H[1];
		delete_heap();
		
		for ( i = 0 ; i < A[nod].size() ; ++i ){
			int nd = A[nod][i].nod;
			int cst = A[nod][i].cst;
			if ( D[nod] + cst < D[nd] ){
				D[nd] = D[nod] + cst;
				if ( Poz[nd] ){
					urca(Poz[nd]);
				}
				else{
					++L;
					H[L] = nd; Poz[H[L]] = L;
					urca(L);
				}
			}
			
		}
	}
	
	for ( i = 2 ; i <= N ; ++i ){
		if ( D[i] == INF )
			g << "0 ";
		else
			g << D[i] << " ";
	}
	
	f.close();
	g.close();
	
	return 0;
}