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

int n, m, viz[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 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;
	for(i=2; i<=n; i++) d[i] = INF;
	nrsel = 0;
	while(nrsel < n){
		min = INF;
		for(i=1; i<=n; i++)
			if(!viz[i] && d[i] < min)
				min=d[i], pmin=i;
		viz[pmin] = 1;
		nrsel++;
		for(p=G[pmin]; p; p=p->urm)
			if(!viz[p->inf] && d[pmin] + p->cost < d[p->inf])
					 d[p->inf] = d[pmin] + p->cost;
	}
}


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;
}