#include<iostream>
#include<queue>
#include<vector>
#include<fstream>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int LIM = 50005;
const int oo = 0x3f3f3f;


vector<pair<int, int>> Graf[LIM];
int D[LIM],N,M;
bool Incoada[LIM];
struct compara
{
	bool operator()(int x, int y)
	{
		return D[x] > D[y];
	}
};
priority_queue<int, vector<int>, compara> coada;

void citire()
{
	f >> N >> M;
	for (int i = 1; i <= M; i++)
	{
		int x, y, cost;
		f >> x >> y >> cost;
		Graf[x].push_back({ y,cost });
	}
	for (int i = 1; i <= N; i++)
		D[i] = oo;
}
void Dijkstra(int nod_start)
{
	D[nod_start] = 0;
	coada.push(nod_start);
	Incoada[nod_start] = true;
	while (!coada.empty())
	{
		int nod = coada.top();
		coada.pop();
		Incoada[nod] = false;
		for (auto it : Graf[nod])
		{
			int Vecin = it.first;
			int Cost = it.second;
			if (D[nod] + Cost < D[Vecin])
			{
				D[Vecin] = D[nod] + Cost;
				if (!Incoada[Vecin])
				{
					coada.push(Vecin);
					Incoada[Vecin] = true;
				}
			}
		}
	}
}

void Afisare()
{
	for (int i = 2; i <= N; i++)
		if (D[i] != oo)
			g << D[i] << " ";
		else
			g << "0 ";
}

int main()
{
	citire();
	Dijkstra(1);
	Afisare();
}