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

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

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));
	}
	
	for (i = 2; i <= n; i ++)
		cnt[i] = infinit;
	
	q[1] = 1;
	fst[1] = 1;
	st = 1, end = 1;
	
	while (st <= end){
		nod = q[st];
		
		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[++end] = nxt, fst[nxt] = 1;
			}
		}
		
		fst[nod] = 0;
		st ++;
	}
	
	
	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;
}