#include <bits/stdc++.h>
#define N 50004
#define pp pair<int, int>

using namespace std;
int n, m, d[N];
vector<pp> G[N];

class comp
{
public:
	bool operator()(pp a, pp b)
	{
		return d[a.first] > d[b.first];
	}
};

priority_queue<pp, vector<pp >, comp> Q;

void dijkstra()
{
	int y, i, s;
	pp p;

	for (i = 2; i <= n; i++) d[i] = INT_MAX;

	Q.push(make_pair(1, 0));
	while (!Q.empty())
	{
		p = Q.top();
		Q.pop();
		if (d[p.first] != p.second) continue;

		s = p.first;
		for (auto x: G[s])
		{
			y = x.first;
			if (d[y] > d[s] + x.second)
			{
				d[y] = d[s] + x.second;
				Q.push(make_pair(y, d[y]));
			}
		}
	}
}

int main()
{
	freopen ("dijkstra.in", "r", stdin);
	freopen ("dijkstra.out", "w", stdout);
	scanf("%i%i", &n, &m);
	int i, x, y, c;
	for (i = 1; i <= m; i++)
	{
		scanf("%i%i%i", &x, &y, &c);
		G[x].push_back(make_pair(y, c));
	}

	dijkstra();
	for (i = 2; i <= n; i++)
		printf("%i ", d[i] == INT_MAX ? 0 : d[i]);
	return 0;
}