#include <stdio.h>
#include <vector>

const int inf = 1 << 30;

using namespace std;

int d[50001], h[50001], ph[50001], n, m; 

void riseup(int);
void godown(int);

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

	int i, a, b, c, sz;
	vector<int> v[50001], cost[50001];

	scanf("%d %d", &n, &m);

	for(i = 1; i <= m; ++i)
	{
		scanf("%d %d %d", &a, &b, &c);
		v[a].push_back(b);
		cost[a].push_back(c);
	}
	for(i = 1; i <= n; ++i)
	{
		d[i] = inf;
		h[i] = ph[i] = i;
	}
	d[1] = 0;
	h[0] = n;
	while(h[0])
	{
		sz = v[h[1]].size();
		for(i = 0; i < sz; ++i)
		{
			if(d[v[h[1]][i]] > d[h[1]] + cost[h[1]][i])
			{
				d[v[h[1]][i]] = d[h[1]] + cost[h[1]][i];
				riseup(ph[v[h[1]][i]]);
			}
		}
		h[1] = h[h[0]];
		ph[h[1]] = 1;
		--h[0];
		godown(1);
	}
	for(i = 2; i <= n; ++i)
	{
		if(d[i] == inf)
			d[i] = 0;
		printf("%d ", d[i]);
	}

	return 0;
}

void godown(int pos)
{
	int l = pos << 1, r = l + 1, best = pos;

	if(l <= h[0] && d[h[l]] < d[h[best]])
	{
		best = l;
	}
	if(r <= h[0] && d[h[r]] < d[h[best]])
	{
		best = r;
	}
	if(best != pos)
	{
		int temp;
		temp = h[best];
		h[best] = h[pos];
		h[pos] = temp;
		ph[h[pos]] = pos;
		ph[h[best]] = best;
		godown(best);
	}
}

void riseup(int pos)
{
	int dad = pos >> 1;;
	if(dad)
	{
		if(d[h[pos]] < d[h[dad]])
		{
			int temp;
			temp = h[pos];
			h[pos] = h[dad];
			h[dad] = temp;
			ph[h[pos]] = pos;
			ph[h[dad]] = dad;
			riseup(dad);
		}
	}
}