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

using namespace std;

#define pb push_back
#define lg 50005
#define infinit 0x3f3f3f3f

int n, m, x, y, cst, i, nr[lg], val, nod, j, cnt[lg], car[lg], pz, nxt, tr[lg];

//typedef pair<int, int> graf;
//vector<graf> v[lg];
int *v[lg], *vn[lg];
struct heap{
	int v, i;
};
heap hp[lg];

int gsnod(int i){
	if (i < n/2){
		if (hp[2*i].v < hp[2*i+1].v)
			return 2*i;
		return 2*i+1;
	}
	return 2*i;
}
void arj(int i){
	int nxt = gsnod(i), aux;
	
	if (i <= n/2)
		if (hp[i].v > hp[nxt].v){
			aux = hp[i].v, hp[i].v = hp[nxt].v, hp[nxt].v = aux;
			
			aux = hp[i].i, hp[i].i = hp[nxt].i, hp[nxt].i = aux;
			
			car[hp[i].i] = i, car[hp[nxt].i] = nxt;
			
			arj(nxt);
		}
}
void arj2(int i){
	int nxt = i/2, aux;
	
	if (i != 1)
		if (hp[i].v < hp[nxt].v){
			aux = hp[i].v, hp[i].v = hp[nxt].v, hp[nxt].v = aux;
			
			aux = hp[i].i, hp[i].i = hp[nxt].i, hp[nxt].i = aux;
			
			car[hp[i].i] = i, car[hp[nxt].i] = nxt;
			
			arj2(nxt);
		}
}
int main()
{
	freopen("dijkstra.in", "rt", stdin);
	freopen("dijkstra.out", "wt", stdout);
	
	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; i ++){
		scanf("%d%d%d", &x, &y, &cst);
		
		nr[x] ++;
		//v[x].pb(graf(y, cst));
		v[x] = (int*)realloc(v[x], (nr[x]+1)*sizeof(int));
		v[x][nr[x]] = y;
		vn[x] = (int*)realloc(vn[x], (nr[x]+1)*sizeof(int));
		vn[x][nr[x]] = cst;
	}
	
	for (i = 1; i <= n; i ++){
		hp[i].i = i;
		hp[i].v = infinit;
		car[i] = i;
	}
	
	hp[1].v = 0;
	for (i = 1; i <= n; i ++){
		val = hp[1].v;
		nod = hp[1].i;
		
		cnt[nod] = val;
		//fprintf(stderr, "am scos nodul %d cu costul %d\n", nod, val);
		
		hp[1].v = infinit+2;
		arj(1);
		tr[nod] = 1;
		
		for (j = 1; j <= nr[nod]; j ++){
			//nxt = v[nod][j].first;
			//cst = v[nod][j].second;
			nxt = v[nod][j];
			cst = vn[nod][j];
			
			pz = car[nxt];
			//fprintf(stderr, "vecinul lui %d este %d cu costul %d ---> %d\n", nod, nxt, val+cst, hp[pz].i);
			if (val + cst < hp[pz].v && !tr[nxt]){
				hp[pz].v = val + cst;
				arj2(pz);
			}
		}
		//fprintf(stderr, "\n");
	}
	
	for (i = 2; i <= n; i ++){
		if (cnt[i] == infinit || cnt[i] == infinit+2)
			cnt[i] = 0;
		printf("%d ", cnt[i]);
	}
	printf("\n");
	
	return 0;
}