/*
 * Autor: Paul Herman
 * Problema: Dijkstra cu heap-uri
 * Data: 14.01.2012
 * Punctaj: -
 * Link: http://www.infoarena.ro/problema/dijkstra
 */
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;

struct muchie
{
	int cost; //Costul pentru a ajunge de la A la B
	unsigned short int b; //Nodul B
};

struct nod
{
	bool vizitat;
	int cost;
	vector<muchie> vecini;
};

#define INFINIT 0x3f3f3f

nod noduri[50001]; //Nodurile grafului
unsigned short int n; //Numarul de noduri
unsigned int m; //Nr. de muchii
vector<int> heap; //Heapul ce pastreaza distanta nodurilor fata de sursa

inline void heap_push(int x)
{
	int pozitie = heap.size();
	int tata = (pozitie - 1) / 2;
	heap.push_back(x);
	while ((tata != pozitie) && (noduri[heap[tata]].cost > noduri[x].cost))
	{
		swap(heap[tata], heap[pozitie]);
		tata = (pozitie - 1) / 2;
	}
}
inline void heap_pop()
{
	swap(heap.front(), heap.back());
	heap.pop_back();
	int modificat = 0;
	int fius, fiud, mic;
	do {
		fius = 2 * modificat + 1;
		fiud = fius + 1;
		mic = modificat;
		if ((fius < heap.size()) && (noduri[heap[fius]].cost < noduri[heap[mic]].cost))
			mic = fius;
		if ((fiud < heap.size()) && (noduri[heap[fiud]].cost < noduri[heap[mic]].cost))
			mic = fiud;
		if (modificat != mic)
			swap(heap[mic], heap[modificat]);
	} while (mic != modificat);
}
inline void heap_print()
{
	for (int i = 0; i < heap.size(); i++)
		cout << heap[i] << ' ';
	cout << '\n';
}
inline bool heap_empty()
{
	return heap.empty();
}
inline int heap_top()
{
	return heap.front();
}
inline void citire()
{
	unsigned short int a;
	muchie b;
	ifstream fin("dijkstra.in");
	fin >> n >> m;
	for (unsigned int i = 1; i <= m ; i++)
	{
		fin >> a >> b.b >> b.cost;
		noduri[a].vecini.push_back(b);
	}
	fin.close();
}
inline void scriere()
{
	ofstream fout("dijkstra.out");
	for (unsigned short int i = 2; i <= n; i++)
		if (noduri[i].vizitat == true)
			fout << noduri[i].cost << " ";
		else
			fout << "0 ";
	fout.close();
}
inline void Dijkstra()
{
	unsigned short int nod_curent = 1;
	noduri[1].cost = 0; //Costul pt. a ajunge la sursa e 0
	heap_push(1);
	for (unsigned short int i = 2; i <= n; i++)
	{
		noduri[i].vizitat = false; //Nu am vizitat nici und nod
		noduri[i].cost = INFINIT; //Costul pt. a ajunge la restul nodurilor e infinit
	}
	while (heap_empty() == false)
	{
		//Cautam nodul nevizitat cel mai apropiat de sursa
		nod_curent = heap_top();
		heap_pop();
		noduri[nod_curent].vizitat = true; //Marcam nodul curent ca vizitat
		for (unsigned short int i = 0; i < noduri[nod_curent].vecini.size(); i++) //Parcurgem toti vecinii nodului curent
		{
			if ((noduri[nod_curent].cost + noduri[nod_curent].vecini[i].cost) < noduri[noduri[nod_curent].vecini[i].b].cost)
			{
				noduri[noduri[nod_curent].vecini[i].b].cost = noduri[nod_curent].cost + noduri[nod_curent].vecini[i].cost;
				heap_push(noduri[nod_curent].vecini[i].b);
			}
		}		
	}
}
int main()
{
	citire();
	Dijkstra();
	scriere();
	return 0;
}