#include<iostream>
#include<fstream>
//#include<windows.h>
#include<queue>
#include<vector>
#define PR pair<int,int>
#define INF 999999999
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

priority_queue<PR, vector<PR>, greater<PR>> pq;
vector<PR> v[50050];
int freq[50050], dist[50050];
int n, m, a, b, c;


int main()
{
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		fin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
	}
	
	//initializare distante
	for (int i = 2; i <= n; i++)
		dist[i] = INF;

	dist[1] = 0;
	pq.push(make_pair(dist[1], 1));

	while (!pq.empty())
	{
		PR aux = pq.top();
		pq.pop();
		if (!freq[aux.second])
		{
			freq[aux.second]++;
			for (int i = 0; i < v[aux.second].size(); i++)
			{
				PR x = v[aux.second][i];
				if (dist[x.first] > dist[aux.second] + x.second)
				{
					dist[x.first] = dist[aux.second] + x.second;
					pq.push(make_pair(dist[x.first], x.first));

				}
			}

		}
	}

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


	//system("pause");
	return 0;
}