#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

#define MAXN 50005
#define MAXC 1024

int N, d[MAXN];

vector< pair<int, int> > con[MAXN];
queue<int> Q[MAXC];

#define Q(i) Q[ (i) & 1023 ]

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

	int M;
	scanf("%d %d", &N, &M);
	for (; M; M--)
	{
		int x, y, cst;
		scanf("%d %d %d", &x, &y, &cst);

		con[x].push_back( make_pair(y, cst) );
	}

	memset( d, 0x3f, sizeof(d) );
	d[1] = 0; Q(0).push(1);

	int left = 1;
	for (int CST = 0; left; CST++)
		for (; !Q(CST).empty(); Q(CST).pop())
		{
			int i = Q(CST).front();
			left--;

			if (d[i] != CST)
				continue;

			vector< pair<int, int> > :: iterator it;
			for (it = con[i].begin(); it != con[i].end(); it++)
				if (d[i] + (*it).second < d[(*it).first])
				{
					d[ (*it).first ] = d[i] + (*it).second;
					Q( d[ (*it).first ] ).push( (*it).first );
					left++;
				}
		}

	for (int i = 2; i <= N; i++)
		if (d[i] == 0x3f3f3f3f)
			printf("0 ");
		else
			printf("%d ", d[i]);
	printf("\n");

	return 0;
}