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

FILE *in  = fopen("dijkstra.in","r");
FILE *out = fopen("dijkstra.out","w");

int N, M;

struct NodVecin {
	unsigned short int Distanta;
	unsigned int Vecin;
} nod;
vector<NodVecin> Graf[NMAX];
vector<int> dist(NMAX, INFINIT);
vector<int>	tata(NMAX, -1);
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++)
		if(dist[i] != INFINIT)
			fprintf(out, "%d ", dist[i]);
			//fout<<dist[i]<<' ';	
		else fprintf(out, "0 "); //fout<<0<<' ';
	//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;
			}
		}
		*/
		for(int j=0; j<Graf[VarfMinim].size(); j++)
			if(!Vizitat[Graf[VarfMinim][j].Vecin] && dist[Graf[VarfMinim][j].Vecin] > DrumMinim + Graf[VarfMinim][j].Distanta) 
			{
				dist[Graf[VarfMinim][j].Vecin] = DrumMinim + Graf[VarfMinim][j].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;
	fscanf(in, "%d %d", &N, &M);
	int x;
	for(int i=1; i<=M; i++) {
		//fin>>x>>nod.Vecin>>nod.Distanta;
		fscanf(in, "%d %d %d", &x, &nod.Vecin, &nod.Distanta);
		Graf[x].push_back(nod);
	}
	//fin.close();
}