//#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
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);
vector<int>	tata(NMAX, -1);
bool Vizitat[NMAX];

// nodul din care pornsesc 
short NodStart = 1;

void citire();
void init();
void dijkstra();
void afiseazaDrum(int);

int main() 
{
	citire();
	init();
	dijkstra();
	
	//cout<<"Distante: ";
	ofstream fout("dijkstra.out");
	for(int i=2; i<=N; i++)
		if(dist[i] != INFINIT)
			fout<<dist[i]<<' ';	
		else fout<<0<<' ';
	fout.close();
	
	/*int nd = 3;
	
	while(nd > 1) {
		cout<<tata[nd]<<' ';
		nd = tata[nd];
	}	
	
	afiseazaDrum(3);*/
}

/*void afiseazaDrum(int nodDestinatie) 
{
	// afisez recursiv drumul bazat de la NodStart la nodDestinatie
	if(nodDestinatie > 1)
		afiseazaDrum(tata[nodDestinatie]);
	cout<<nodDestinatie<<' ';
}*/

void dijkstra() {
	int NodCurent = 0;
	
	dist[NodStart] = 0;
	
	// ma folosesc de o coada
	queue <int> Q;
	
	// nodul de start - il vizitez
	Q.push(NodStart);
	Vizitat[NodStart] = true;
	
	while(!Q.empty())
	{
		// iau primul element din coada
		NodCurent = Q.front();
		// il sterg din coada
		Q.pop();
		// nodul devine nevizitat
		Vizitat[NodCurent] = false;
		
		// actualizez distantele de la nodCurent la fiecare vecin al lui
		vector<NodVecin> :: iterator it;
		for(it = Graf[NodCurent].begin(); it != Graf[NodCurent].end(); ++it)
		{
			// daca am un drum mai mic decat cel existent
			if(dist[NodCurent] + it->Distanta < dist[it->Vecin]) 
			{
				// am gasit un drum mai mic
				dist[it->Vecin] = dist[NodCurent] + it->Distanta;
				// adaug nodul in coada ca sa-i vizitez vecinii numai daca nu exista deja 
				if(!Vizitat[it->Vecin])
				{
					Q.push(it->Vecin);
					// ca sa nu il mai pun inca odata
					Vizitat[it->Vecin] = true;
				}
			}
		}
	}
}

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;
		tata[i->Vecin] = NodStart;
	}*/
	tata[NodStart] = 0;
}

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();
}