#include<iostream> 
#include<fstream>
#include<vector>
#include<queue>

using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

const int INF = 1e9;
vector<pair<int,int>> lista_adiacenta[50005];
int dist[50005];



int main()
{
	int n, m, start, i, a, b, c;
	cin >> n >> m; 
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b >> c;
		lista_adiacenta[a].push_back({ b, c });
	}

	for (int i = 1; i <= n; i++)
		dist[i] = INF;
	dist[1] = 0;

	priority_queue<
		pair<int, int>,
		vector<pair<int, int>>,
		greater<pair<int, int>>
	>pq;

	pq.push({ 0, 1 });

	while (!pq.empty())
	{
		int d = pq.top().first;
		int nod = pq.top().second;
		pq.pop();

		if (d != dist[nod])
			continue;

		for (auto& edge : lista_adiaceta[nod])
		{
			int vecin = edge.first;
			int cost = edge.second;

			if (dist[vecin] > dist[nod] + cost)
			{
				dist[vecin] = dist[nod] + cost;
				pq.push({ dist[vecin], vecin });
			}
		}
	}

	for (int i = 2; i <= n; i++)
	{
		if (dist[i] == INF)
			cout << 0 << " ";
		else
			cout << dist[i] << " ";
	}

	return 0;
}