#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair
#define MAXN 50100
#define INF 1000000000

int N, M, d[MAXN]; vector<int> G[MAXN], C[MAXN];
set< pair<int, int> > T;

void solve(void)
{
	int i, j, k, val, x;

	for (i = 2; i <= N; i++) d[i] = INF;
	T.insert(mp(0, 1));

	while (T.size() > 0)
	{
		val = (*T.begin()).first, x = (*T.begin()).second;
		T.erase(*T.begin());
		for (i = 0; i < G[x].size(); i++)
			if (d[G[x][i]] > val + C[x][i])
				d[G[x][i]] = val + C[x][i], T.insert(mp(d[G[x][i]], G[x][i]));
	}
}

int main(void)
{
	freopen("dijkstra.in", "rt", stdin);
	freopen("dijkstra.out", "wt", stdout);

	int i, a, b, c;

	scanf("%d %d\n", &N, &M);

	for (i = 1; i <= M; i++)
		scanf("%d %d %d\n", &a, &b, &c), G[a].pb(b), C[a].pb(c);

	solve();

	for (i = 2; i <= N; i++)
		printf("%d ", d[i] == INF ? 0 : d[i]);

	return 0;
}