#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
#define inf 1<<30
#define maxn 50010

using namespace std;

int n, m;
vector<pair<int, unsigned int> > a[maxn];

priority_queue< pair<int, int> > pq;
bitset<maxn> inqueue;
int d[maxn];

void djikstra()
{
	for (int i = 2; i <= n; i++)
		d[i] = inf;

	d[1] = 0;
	inqueue[1] = 1;
	pq.push(make_pair(1, 0));
	while (pq.size() > 0)
	{
		int nod = pq.top().first;
		pq.pop();
		inqueue[nod] = false;
		for (int i = 0; i < a[nod].size(); i++)
		{
			int nodc = a[nod][i].first;
			int costc = a[nod][i].second;
			if (d[nodc] > d[nod] + costc)
			{
				d[nodc] = d[nod] + costc;
				if (inqueue[nodc] == 0)
				{
					pq.push(make_pair(nodc, d[nodc]));
					inqueue[nodc] = 1;
				}
			}
		}
	}
}

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d %d", &n, &m);
	int x, y, z;
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d%d", &x, &y, &z);
		a[x].push_back(make_pair(y, z));
	}
	djikstra();
	for (int i = 2; i <= n; i++)
	{
		printf("%d ", d[i] == inf ? 0 : d[i]);
	}
}