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

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], pz, nxt, st, end;
bool fst[lg];

typedef pair<int, int> graf;
vector<graf> v[lg];
queue<int> q;

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);
	
	scanf("%d%d\n", &n, &m);
	for (i = 1; i <= m; i ++){
		//scanf("%d%d%d", &x, &y, &cst);
		citire();
		
		nr[x] ++;
		v[x].pb(graf(y, cst));
	}
	
	for (i = 2; i <= n; i ++)
		cnt[i] = infinit;
	//memset(cnt, 0x3f, sizeof(int)*(n+1));
	cnt[1] = 0;
	
	q.push(1);
	fst[1] = true;
	st = 1, end = 1;
	
	while (!q.empty()){
		nod = q.front();
		q.pop();
		
		for (i = 0; i < nr[nod]; i ++){
			nxt = v[nod][i].first;
			cst = v[nod][i].second;
			
			if (cst + cnt[nod] < cnt[nxt]){
				cnt[nxt] = cst + cnt[nod];
				
				if (!fst[nxt]){
					q.push(nxt);
					fst[nxt] = true;
				}
			}
		}
		
		fst[nod] = false;
	}
	
	
	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;
}