#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<list>
#include<set>
#include<limits.h>
using namespace std;
int main()
{
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");

	int nrOfNodes,nrOfEdges;
	fin >> nrOfNodes;
	fin >> nrOfEdges; 

	int *dist = new int[nrOfNodes + 1];
	int *prev = new int[nrOfNodes + 1];
	int source = 1;
	dist[source] = prev[source] = 0;
	for (int i = 2; i <= nrOfNodes; i++)
		dist[i] = INT32_MAX, prev[i] = 0;
	list<pair<int, int>> *adjList = new list<pair<int, int>>[nrOfNodes + 1];
	for (int i = 0; i < nrOfEdges; i++)
	{
		int x, y, d;
		fin >> x >> y >> d;
		adjList[x].push_back(make_pair(d, y));
	}

	set < pair<int, int>> S;
	S.insert(make_pair(0, source));
	while (!S.empty())
	{
		int current = S.begin()->second;
		S.erase(S.begin());
		for (list<pair<int, int>>::iterator p = adjList[current].begin(); p != adjList[current].end(); p++)
		{
			if (dist[p->second] > dist[current] + p->first) 
			{
				if (p->first != INT32_MAX)
				{
					S.erase(make_pair(dist[p->second],p->second));
				}
				dist[p->second] = dist[current] + p->first;
				prev[p->second] = current;
				S.insert(make_pair(dist[p->second], p->second));
			}
		}
	}
	for (int i = 2; i <= nrOfNodes; i++)
		if (dist[i] == INT32_MAX)
			fout << 0 << " ";
		else
		fout << dist[i] << " ";

	return 0;
}