#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>

#define INPUT_FILE "dijkstra.in"
#define OUTPUT_FILE "dijkstra.out"

#define MAXIM_VARFURI 50000

#define INFINIT 0x3f3f3f

using namespace std;

int numar_varfuri,
	numar_muchii;

vector < pair < int , int > > lista_de_adiacenta[MAXIM_VARFURI];
vector < pair < int , int > > :: iterator iterator_lista_adiacenta;

int drum_minim[MAXIM_VARFURI], vizitat[MAXIM_VARFURI];

void citire()
{
	ifstream fin(INPUT_FILE, ios::in);
	int auxiliar1,
		auxiliar2,
		auxiliar3;

	fin >> numar_varfuri >> numar_muchii;

	while( fin >> auxiliar1 >> auxiliar2 >> auxiliar3 )
		lista_de_adiacenta[auxiliar1].push_back(make_pair(auxiliar2, auxiliar3));
}

void dijkstra(int nod)
{
	queue < int > coada;

	memset(drum_minim, INFINIT, sizeof(drum_minim));

	drum_minim[nod] = 0;

	coada.push(nod);

	vizitat[nod] = 1;

	while(!coada.empty())
	{
		int nod_curent = coada.front();
		coada.pop();
		vizitat[nod_curent] = 0;
		for(iterator_lista_adiacenta = lista_de_adiacenta[nod_curent].begin(); iterator_lista_adiacenta != lista_de_adiacenta[nod_curent].end(); ++iterator_lista_adiacenta)
		{
			if(drum_minim[nod_curent] + iterator_lista_adiacenta->second < drum_minim[iterator_lista_adiacenta->first])
			{
				drum_minim[iterator_lista_adiacenta->first] = drum_minim[nod_curent] + iterator_lista_adiacenta->second;
				if(!vizitat[iterator_lista_adiacenta->first])
				{
					coada.push(iterator_lista_adiacenta->first);
					vizitat[iterator_lista_adiacenta->first] = 1;
				}
			}
		}
	}

}

void afisare()
{
	ofstream fout(OUTPUT_FILE);
	for(int i = 2; i <= numar_varfuri; ++i)
		fout << (drum_minim[i] < INFINIT ? drum_minim[i]:0) << " " ;
	fout << '\n';
}

int main()
{
	citire();
	dijkstra(1);
	afisare();
	return 0;
}