// Dijkstra.cpp : Defines the entry point for the console application.
//

#include <fstream>
#include <vector>
#include <stdlib.h>
#include <queue>
#include <utility>
#define Nmax 50003
using namespace std;

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

class pereche
{
public:
	int first, second;
	bool  operator < (const  pereche& x)const ;

};
bool pereche::operator< (const  pereche &  x) const
{
	return second > x.second;
}

vector <pair<int,long long>> v[Nmax];
int n, m;
void Citire()
{
	int i,x,y,z;

	fin >> n>>m;
	for (i = 1; i <= m; ++i)
	{
		fin >> x >> y>>z;
		v[x].push_back({ y,z });

	}

}


void Dijkstra()
{
	priority_queue <pereche> d1;
	int i, distante[Nmax];
	const int inf = 2000000000;
	int viz[Nmax] = { 0 };

	for (i = 1; i <= n; i++)
		distante[i] = inf;
		distante[1] = 0;
		viz[1] = 1;

		for (pair<int, long long> it : v[1])
		{
			distante[it.first] = it.second;
			pereche w;
			w.first = it.first;
			w.second = it.second;
			d1.push(w);
		}


		for (i = 1; i < n; i++) //execut n-1 pasi de genul: gasesc distanta minima din vectorul de distante si incerc sa calculez noi distante prin intermediul acestuia
		{

			pereche element = d1.top();
			while (viz[element.first] == 1)
			{
				d1.pop();
				element = d1.top();
			}
			d1.pop();
			if (element.second!=inf)
			for (pair<int, long long> it : v[element.first])
			{
				if (element.second + it.second < distante[it.first]) {
					distante[it.first] = element.second + it.second;
					pereche aux;
					aux.first = it.first;
					aux.second = distante[it.first];
					d1.push(aux);

				}
			}
		}

		for (i = 2; i <= n; i++)
			fout << distante[i] << " ";

}

int main()
{

	Citire();
	Dijkstra();
    return 0;
}