#include <stdio.h>
#define MAXN 50001
#define INF 50000100L

int n, m, h[MAXN], nh, poz[MAXN];
long d[MAXN];
struct nod{
	int inf, cost;
	nod *urm;
} *G[MAXN];

void add(nod *&p, int x, int c){
	nod *q = new nod;
	q->inf = x;
	q->cost = c;
	q->urm = p;
	p = q;
}

void upheap(int i){
	int p=i, aux;
	while(p>1 && d[ h[p/2] ] > d[ h[p] ]){
		aux = h[p], h[p] = h[p/2], h[p/2] = aux;
		aux = poz[ h[p] ], poz[ h[p] ] = poz[ h[p/2] ], poz[ h[p/2] ] = aux;
		p /= 2;
	}
}

void downheap(int i){
	int p=i, p_nou, aux;
	while(2*p<=nh){
		p_nou = 2*p;
		if(2*p+1 <= nh)
			if(d [h[p_nou] ] > d[ h[2*p+1] ]) p_nou = 2*p+1;
		if(d[ h[p] ] > d[ h[p_nou] ]){
			aux = h[p], h[p] = h[p_nou], h[p_nou] = aux;
			aux = poz[ h[p] ], poz[ h[p] ] = poz[ h[p_nou] ], poz[ h[p_nou] ] = aux;
		}
		p = p_nou;
	}
}

void read(){
	int i, x, y, c;
	FILE *f=fopen("dijkstra.in", "r");
	fscanf(f, "%d %d", &n, &m);
	for(i=0; i<m; i++){
		fscanf(f, "%d %d %d", &x, &y, &c);
		add(G[x], y, c);
	}
}

void dijkstra(){
	int i, nrsel, pmin;
	long min;
	nod *p;
	d[1] = 0; h[1] = 1; poz[1]=1;
	for(i=2; i<=n; i++) d[i] = INF, poz[i] = h[i] = i;
	nh = n;
	nrsel = 0;
	while(nrsel < n){

		min = d[h[1]];
		pmin = h[1];
		poz[h[1]]=-1;
		poz[h[nh]] = 1;
		h[1] = h[nh--];
		downheap(1);

		nrsel++;

		for(p=G[pmin]; p; p=p->urm)
			if(poz[p->inf]>0 && d[pmin] + p->cost < d[p->inf]){
					 d[p->inf] = d[pmin] + p->cost;
					 upheap(poz[p->inf]);
			}
	}
}


void afis(){
	int i;
	FILE *g=fopen("dijkstra.out", "w");
	for(i=2; i<=n; i++)
		fprintf(g, "%ld ", d[i]==INF ? 0 : d[i]);
	fclose(g);
}



int main(){
	read();
	dijkstra();
	afis();
	return 0;
}