#include <fstream>
#include <bitset>
#include <algorithm>
using namespace std;
const int inf = 1 << 30;
struct node{
	int  info, cost;
	node* next;
};
int H[50001], d[50001], N, M, a, b, c, P[50001], cnt = 0;
bitset<50001> v;
node* No[50001];
ifstream f("dijkstra.in");
ofstream of("dijkstra.out");
void per(int f){
	int t = f >> 1;
	if (t >= 1)
	if (d[H[t]] > d[H[f]]){
		swap(H[t], H[f]);
		swap(P[H[t]], P[H[f]]);
		per(t);
	}
}
void sift(int f){
	int t = f;
	if (t <= cnt / 2){
		if (d[H[t * 2]] < d[H[t]])t = t * 2;
		if (f != t && t + 1 <= cnt)if (d[H[t]]>d[H[t + 1]])t = t + 1;
		else if (f == t&&t * 2 + 1 <= cnt)if (d[H[t]] > d[H[t * 2 + 1]])t = t * 2 + 1;
		if (f != t){
			swap(H[t], H[f]);
			swap(P[H[t]], P[H[f]]);
			sift(t);
		}
	}
}
void add(int x){
	H[++cnt] = x;
	P[x] = cnt;
	per(cnt);
}
int rad(){
	int x = H[1];
	swap(H[1], H[cnt]);
	P[H[1]] = 1;
	--cnt;
	sift(1);
	return x;
}
int main(){
	f >> N >> M;
	d[1] = 0;
	for (int i = 2; i <= N; ++i)
		d[i] = inf;
	for (int i = 1; i <= M; ++i){
		f >> a >> b >> c;
		node* p = new node();
		p->info = b;
		p->cost = c;
		p->next = No[a];
		No[a] = p;
	}
	add(1);
	v[1] = 1;
	while (cnt){
		int x = rad();
		for (node*p = No[x]; p != 0; p = p->next)
		if (!v[p->info] || d[p->info] > d[x] + p->cost){
			v[p->info] = 1;
			d[p->info] = d[x] + p->cost;
			if (!P[p->info])add(p->info);
			else per(P[p->info]);
		}
	}
	for (int i = 2; i <= N; ++i)
	if (d[i] == inf)of << 0 << " ";
	else of << d[i] << " ";
}