#include <stdio.h>
#include <vector>
#include <set>
using namespace std;

vector <pair<long, long> > graf[50001];
set <pair<long, long> > q;

long visited[50001], rez[50001], node, cost, old_value, new_value, vecin, a, b, c, n, m;

int main()
{
	freopen ("dijkstra.in", "rt", stdin);
	freopen ("dijkstra.out", "wt", stdout);
	
	scanf("%ld %ld", &n, &m);
	for (long i = 1; i <= m; ++i)
	{
		scanf("%ld %ld %ld", &a, &b, &c);
		graf[a].push_back(make_pair(b, c));
	}

	for (long i = 2; i <= n; ++i)
		rez[i] = 2147000000;

	q.insert(make_pair(0, 1));

	while (!q.empty())
	{
		node = q.begin()->second;
		cost = q.begin()->first;
		q.erase(q.begin());

		for (long i = 0; i < graf[node].size(); ++i)
		{
			vecin = graf[node][i].first;
			old_value = rez[vecin];
			new_value = graf[node][i].second + rez[node];
			

			if (new_value < old_value)
			{
				rez[vecin] = new_value;
				if (q.find(make_pair(old_value, vecin)) != q.end())
					q.erase(q.find(make_pair(old_value, vecin)));
				q.insert(make_pair(new_value, vecin));
			}
		}
	}

	for (long i = 2; i <= n; ++i)
		if (rez[i] != 2147000000)
			printf("%ld ", rez[i]);
		else	
			printf("0 ");
	printf("\n");
	return 0;
}