//#include<stdio.h>
#include<fstream>
#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];
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);
		}
}
void citire(){
	int kkt = 0, j, nt;
	char sir[50];
	fgets(sir, 50, stdin), nt = 0;
	
	for (j = nt; sir[j] <= '9' && sir[j] >= '0'; j ++)
		kkt = kkt*10+sir[j]-'0';
	x = kkt, kkt = 0;
	nt = j+1;
	for (j = nt; sir[j] <= '9' && sir[j] >= '0'; j ++)
		kkt = kkt*10+sir[j]-'0';
	y = kkt, kkt = 0;
	nt = j+1;
	for (j = nt; sir[j] <= '9' && sir[j] >= '0'; j ++)
		kkt = kkt*10+sir[j]-'0';
	cst = kkt;
}
int main()
{
	/*
	freopen("dijkstra.in", "rt", stdin);
	freopen("dijkstra.out", "wt", stdout);
	*/
	ifstream in("dijkstra.in");
	ofstream out("dijkstra.out");
	
	//scanf("%d%d\n", &n, &m);
	in>> n>> m;
	for (i = 1; i <= m; i ++){
		//scanf("%d%d%d", &x, &y, &cst);
		//citire();
		in>> x>> y>> cst;
		
		nr[x] ++;
		v[x].pb(graf(y, 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 = 0; j < nr[nod]; j ++){
			nxt = v[nod][j].first;
			cst = v[nod][j].second;
			
			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]);
		out<< cnt[i] <<' ';
	}
	//printf("\n");
	out<< '\n';
	
	return 0;
}