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

vector <pair <long, long> > g[50001];
set <pair <long, long> > thingy;

long n, m, i, a, b, c, nod, cost_, cost[50001];

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

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

	for (i = 1; i <= n; ++i)
		cost[i] = 2147000000;

	thingy.insert(make_pair(0, 1));
	cost[1] = 0;

	while (!thingy.empty())
	{
		//set <pair <long, long> >::iterator it;
		//it = thingy.begin();

		nod = thingy.begin() -> second;
		cost_ = thingy.begin() -> first;

		thingy.erase(thingy.begin());

		for (vector <pair <long, long> >::iterator it = g[nod].begin(); it < g[nod].end(); ++it)
		{
			if (cost[nod] + (*it).second < cost[(*it).first])
			{
				cost[(*it).first] = cost[nod] + (*it).second;
				thingy.insert(make_pair(cost[(*it).first], (*it).first));
			}
		}
	}	

	for (i = 2; i <= n; ++i)
		printf("%ld ", cost[i] != 2147000000 ? cost[i] : 0);
	printf("\n");

	return 0;
}