#include <cstdio>
#include <vector>
#define maxn 50100
#define inf 1000000000

using namespace std;

int n, m, i, j, a, b, c, p, u, nod, fiu;
int coa[2 * maxn], viz[maxn], cmin[maxn];
vector <int> g[maxn], cs[maxn];

int main() {
	freopen("grader_test9.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; i++) {
		scanf("%d%d%d", &a, &b, &c);
		g[a].push_back(b);
		cs[a].push_back(c);
	}

	int ok = 1;

	p = 1; u = 1;
	coa[1] = 1;
	cmin[1] = 0;
	viz[1] = 1;
	
	for (i = 2; i <= n; i++)
		cmin[i] = inf;

	while (p <= u) {
		nod = coa[p];
		viz[nod] = 0;

		for (i = 0; i < g[nod].size(); i++) {
			fiu = g[nod][i];
			if (cmin[fiu] > cmin[nod] + cs[nod][i]) {
				cmin[fiu] = cmin[nod] + cs[nod][i];

				if (viz[fiu] == 0) {
					u++;
					if (u > 75000)
						u -= 75000;
					coa[u] = fiu;
					viz[fiu] = 1;
				}
			}
		}
		p++;
		if (p > 75000)
			p -= 75000;
	}

	for (i = 2; i <= n; i++)
		if (cmin[i] == inf)
			printf("0 ");
		else
			printf("%d ", cmin[i]);

	return 0;
}