#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#define MAX INT_MAX;
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n, m;
int costuri[50001];
bool viz[50001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
vector<pair<int, int>>adiacenta[50001];
int main()
{
	f >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int nr1, nr2, cost;
		f >> nr1 >> nr2 >> cost;
		adiacenta[nr1].push_back({ nr2,cost });
	}

	for (int i = 1; i < 50001; i++)
		costuri[i] = MAX;
	costuri[1] = 1;
	q.push({ 1,1 });
	while (!q.empty())
	{
		int nod_curent = q.top().second;
		int cost_curent = q.top().first;
		q.pop();
		if (viz[nod_curent])
			continue;

		viz[nod_curent] = 1;
		for (auto x : adiacenta[nod_curent])
		{
			if (costuri[x.first] > cost_curent + x.second)
			{
				costuri[x.first] = cost_curent + x.second;
				viz[x.first] = 1;
				q.push({ costuri[x.first],x.first });
			}
		}
	}
	for (int i = 2; i <= n; i++)
	{
		if (costuri[i] == INT_MAX)
		{
			g << 0 << " ";
		}
		else
			g << costuri[i] - 1<< " ";
	}
}