#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], nxt, tr[lg];

typedef pair<int, int> graf;
vector<graf> v[lg];
typedef pair<int, int> heap;
heap ct;

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;
}
class mmc{
public:
	bool operator()(heap jos, heap sus){
		return (jos.second > sus.second);
	}
};

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));
	}
	
	priority_queue< heap, vector<heap>, mmc> hp;
	
	memset(cnt, 0x3f, (n+1)*sizeof(int));
	cnt[1] = 0;
	
	hp.push(heap(1, 0));
	for (i = 2; i <= n; i ++)
		hp.push(heap(i, infinit));
	
	while (!hp.empty()){
		
		ct = hp.top();
		hp.pop();
		
		if (cnt[ct.first] == ct.second){
			nod = ct.first;
			val = ct.second;
			tr[nod] = 1;
			
			for (j = 0; j < nr[nod]; j ++){
				nxt = v[nod][j].first;
				cst = v[nod][j].second;
				
				if (val + cst < cnt[nxt] && !tr[nxt]){
					cnt[nxt] = val + cst;
					hp.push(heap(nxt, cnt[nxt]));
				}
			}
		}
	}
	
	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;
}