#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int NMAX = 50005;
const int oo = (1 << 30);
int n, m;
int D[NMAX];
bool viz[NMAX];
vector < pair < int, int > > v[NMAX];
struct comparaDistante
{
	bool operator()(int x, int y)
	{
		return D[x] > D[y];
	}
};
priority_queue < int, vector < int >, comparaDistante> Coada;
void Citeste()
{
	f >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, c;
		f >> x >> y >> c;
		v[x].push_back(make_pair(y, c));
	}
}
void Dijkstra(int nodStart)
{
	for (int i = 1; i <= n; i++)
		D[i] = oo;

	D[nodStart] = 0;
	Coada.push(nodStart);
	viz[nodStart] = true;
	while (!Coada.empty())
	{
		int nodCurent = Coada.top();
		Coada.pop();
		viz[nodCurent] = false;

		for (int i = 0; i < v[nodCurent].size(); i++)
		{
			int Vecin = v[nodCurent][i].first;
			int Cost = v[nodCurent][i].second;
			if (D[nodCurent] + Cost < D[Vecin])
			{
				D[Vecin] = D[nodCurent] + Cost;
				if (viz[Vecin] == false)
				{
					Coada.push(Vecin);
					viz[Vecin] = true;
				}
			}
		}
	}
}
void Afiseaza()
{
	for (int i = 2; i <= n; i++)
	{
		if (D[i] != oo)
			g << D[i] << " ";
		else
			g << "0 ";
	}
}
int main()
{
	Citeste();
	Dijkstra(1);
	Afiseaza();
	return 0;
}