//#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define NMAX 50001
#define INFINIT 9876543

int N, M;

struct NodVecin {
	unsigned short int Distanta;
	unsigned int Vecin;
} nod;
vector<NodVecin> Graf[NMAX];
vector<int> dist(NMAX, INFINIT);
bool Vizitat[NMAX];

// nodul din care pornsesc 
short NodStart = 1;

void citire();
void init();
void dijkstra();

int main() 
{
	citire();
	init();
	dijkstra();
	
	//cout<<"Distante: ";
	ofstream fout("dijkstra.out");
	for(int i=2; i<=N; i++)
		fout<<dist[i]<<' ';	
	fout.close();
}

void dijkstra() {
	int VarfMinim, DrumMinim;
	// se repeta de N-1 ori
	for(int k = 1; k < N; k++)
	{
		// caut nodul cel mai apropiat de NodStart nevizitat
		DrumMinim = INFINIT;
		for(int i=1; i<=N; i++) 
		{
			if(!Vizitat[i] && dist[i] < DrumMinim) 
			{
				DrumMinim = dist[i];
				VarfMinim = i;
			}
		}
		
		// am gasit cel mai apropiat nod nevizitat 
		Vizitat[VarfMinim] = true;
		
		// fac update la distantele tuturor vecinilor nodului 
		vector<NodVecin> :: iterator i;
		for(i = Graf[VarfMinim].begin(); i != Graf[VarfMinim].end(); ++i)
		{
			// daca drumul gasit e mai mic decat drumul deja cunoscut - il modific
			if(!Vizitat[i->Vecin] && dist[i->Vecin] > DrumMinim + i->Distanta)
			{
				dist[i->Vecin] = DrumMinim + i->Distanta;
			}
		}
	}
}

void init()
{
	Vizitat[NodStart]  = true;
	dist[NodStart]     = 0;
	// pun distantele catre nodurile directe din NodStart
	vector<NodVecin> :: iterator i;
	for(i = Graf[NodStart].begin(); i != Graf[NodStart].end(); ++i) 
	{
		dist[i->Vecin] = i->Distanta;
	}
}

void citire() 
{
	ifstream fin("dijkstra.in");
	fin>>N>>M;
	int x;
	for(int i=1; i<=M; i++) {
		fin>>x>>nod.Vecin>>nod.Distanta;
		Graf[x].push_back(nod);
	}
	fin.close();
}