/*
 * Autor: Paul Herman
 * Problema: Bellman-Ford(n*m)
 * Data: 01.10.2011
 */
#include <fstream>
using namespace std;

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

#define INFINIT 0x3f3f3f

unsigned long int noduri[250001]; //Costul pt. a ajunge la fiecare nod
muchie muchii[50001]; //Muchiile grafului
unsigned long int n; //Numarul de noduri
unsigned int m; //Nr. de muchii

void citire()
{
	ifstream fin("dijkstra.in");
	fin >> n >> m;
	for (unsigned int i = 1; i <= m ; i++)
		fin >> muchii[i].a >> muchii[i].b >> muchii[i].cost;
	fin.close();
}
void scriere()
{
	ofstream fout("dijkstra.out");
	for (unsigned long int i = 2; i <= n; i++)
	{
		if (noduri[i] < INFINIT)
			fout << noduri[i] << " ";
		else
			fout << "0 ";
	}
	fout.close();
}
void BF()
{
	noduri[1] = 0; //Costul pt. a ajunge la sursa e 0
	for (unsigned long int i = 2; i <= n; i++)
		noduri[i] = INFINIT; //Costul pt. a ajunge la restul nodurilor e infinit
	for (unsigned long int i = 1; i <= n; i++) //Parcurgem toate nodurile
		for (unsigned int j = 1; j <= m; j++) //Parcurgem toate muchiile
			if ((noduri[muchii[j].a] + muchii[j].cost) < noduri[muchii[j].b])
				noduri[muchii[j].b] = noduri[muchii[j].a] + muchii[j].cost;
}
int main()
{
	citire();
	BF();
	scriere();
	return 0;
}