#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<list>
#include<set>
#include<limits.h>
using namespace std;
struct Vertex
{
	int name;
	int distance;
	int previous;
	Vertex() {}
	Vertex(int val) { name = val; distance = INT32_MAX; previous = NULL; }
	void init(int val) { name = val; distance = INT32_MAX; previous = NULL; }
	/*bool operator < (Vertex B) { return distance < B.distance; }
	bool operator () ( Vertex B) { return distance < B.distance; }*/
};
bool operator < (Vertex A, Vertex B) { return A.distance < B.distance; }
int main()
{
	ifstream fin("dijkstra.in");
	int nrOfNodes,nrOfEdges;
	fin >> nrOfNodes;
	fin >> nrOfEdges; 
//	cout << nrOfNodes << " " << nrOfEdges << endl;
	int i, j;
	vector<Vertex> V(nrOfNodes+1);
	for (i = 1; i <= nrOfNodes; i++)
	{
		Vertex Vert(i);
		V[i]=Vert;
	}
	vector<list<pair<int, int>>> adjList(nrOfNodes+1);
	
	for (i = 0; i < nrOfEdges; i++)
	{
		int x, y, dist;
		fin >> x >> y >> dist;
	//	cout << x << " " << y << " " << dist << endl;
		adjList[x].push_back(make_pair(y, dist));

		}
	int src = 1;
	V[src].previous = NULL;
	V[src].distance = 0;

	set<Vertex> S;
	S.insert(V[src]);
	while (!S.empty())
	{
		
		Vertex current = *S.begin();
		S.erase(S.begin());
		list<pair<int, int>>::iterator p;
		for (p = adjList[current.name].begin(); p != adjList[current.name].end(); p++)
		{
			int v, dist;
			v = p->first; dist = p->second;
			if (V[v].distance > current.distance + dist)
			{
				if (V[v].distance != INT32_MAX)
					S.erase(V[v]);
				V[v].distance = current.distance + dist;
				V[v].previous = current.name;
				S.insert(V[v]);
			}
		}
		

	}

	/*for (int i = 1; i <= nrOfNodes; i++)
		cout << V[i].name << " " << V[i].distance << " "<<V[i].previous << endl;*/
	ofstream fout("dijkstra.out");
	for (i = 2; i <= nrOfNodes; i++)
		if (V[i].distance == INT32_MAX)
			fout << 0 << " ";
		else
			fout << V[i].distance<<" ";
	return 0;
}