#include <algorithm>
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

#define nmax 50001
#define inf 0x3f3f3f3f

#define T (u >> 1)
#define L (u << 1)
#define R (L | 1)

int i, n;

int H[nmax];
int d[nmax];

struct nod {
	int u;
	int cost;
	nod *next;
};
nod *v[nmax];

inline void add(int i, int j, int k) {
	nod *p = new nod;
	p->u = j;
	p->cost = k;
	p->next = v[i];
	v[i] = p;
}
 
inline void upheap(int u) {
	while (u != 1 && d[H[T]] > d[H[u]]) swap(H[T], H[u]), u = T;
}

inline void downheap(int u) {
	while (1) {
		int m = u;
		if (L <= n && d[H[L]] < d[H[m]]) m = L;
		if (R <= n && d[H[R]] < d[H[m]]) m = R;
		if (m == u)
			break;
		swap(H[m], H[u]);
		u = m;
	}
}

int N, M;
int x, a, b, c;

int main() {
	fin >> N >> M;
	for (i = 1; i <= N; ++i) d[i] = inf;
	for (i = 1; i <= M; ++i) {
		fin >> a >> b >> c;
		add(a, b, c);
	}
	d[1] = 0;
	n = 1;
	H[1] = 1;
	while (n) {
		x = H[1];
		for (nod *it = v[x]; it; it = it->next) {
			if (d[x] + it->cost < d[it->u]) {
				d[it->u] = d[x] + it->cost;
				++n;
				H[n] = it->u;
				upheap(n);
			}
		}
		swap(H[1], H[n]);
		--n;
		downheap(1);
	}
	for (i = 2; i <= N; ++i) {
		if (d[i] != inf) fout << d[i] << ' ';
		else 
			fout << "0 ";
	}
	return 0;
}