#include<iostream>
#include<queue>
#define inf 0x3f3f3f3f
using namespace std;
typedef pair<int, int> pii;
const int lim = 5e4 + 4;
int d[lim];
bool inQueue[lim];
struct cmp {
	bool operator()(int a, int b)
	{
		return d[a] > d[b];
	}
};
priority_queue<int, vector<int>, cmp> q;
vector<pii> g[lim];
int n, m;
int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.in", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y,c;
		cin >> x >> y>>c;
		g[x].push_back(make_pair(y, c));
	}
	for (int i = 1; i <= n; i++)
		d[i] = inf;
	d[1] = 0;
	q.push(1);
	inQueue[1] = true;
	while (!q.empty())
	{
		int v = q.top();
		q.pop();
		inQueue[v] = false;
		for (auto it : g[v])
		{
			int u = it.first, cost = it.second;
			if (d[v] + cost < d[u])
			{
				d[u] = d[v] + cost;
				if (!inQueue[u])
				{
					q.push(u);
					inQueue[u] = true;
				}
			}
		}
	}
	for (int i = 2; i <= n; i++)
		cout << d[i] << " ";
}