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

using namespace std;

int n, m;
vector<pair<int, unsigned int> > a[maxn];
priority_queue< pair<int, unsigned 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()
{
	ifstream in("dijkstra.in");
	ofstream out("dijkstra.out");
	in >> n >> m;
	int x, y, z;
	for (int i = 1; i <= m; i++)
	{
		in >> x >> y >> z;
		a[x].push_back(make_pair(y, z));
	}
	djikstra();
	for (int i = 2; i <= n; i++)
	{
		if (d[i] == inf)
			out << "0 ";
		else
			out<<d[i]<<" ";
	}
}