#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
#define nmax 50005
#define inf 1<<30
#define cost first
#define ind second
using namespace std;

int n, m, best[nmax];
bool vizitat[nmax];

vector <int> vecin[nmax], muchie[nmax];
set <pair <int, int> > q;

void dijkstra() {
	pair <int, int> nod;
	int curent, nou, costcurent;
	int potential;
	while(!q.empty()) {
		nod = *q.begin();
		q.erase( *q.begin() );
	
		curent = nod.ind;	
		costcurent = best[curent];

		for(int i=0; i < vecin[curent].size(); i++) {		//iau toti vecinii nevizitati ai nodului curent
			nou = vecin[curent][i];	
			if(vizitat[nou]) continue;
			
			potential = costcurent + muchie[curent][i];	//distanta minima pana la nodul curent + lungimea muchiei dintre curent si vecin
			if(potential < best[nou]) {		
				best[nou] = costcurent + muchie[curent][i];	//daca distanta potentiala-i de preferat, atunci actualizez bestul
				//q.erase(q.find( make_pair(best[nou], nou) ) );		//sterg vecinul din set, pentru ca nu mai are bestul updatat
				q.insert( make_pair( best[nou], nou ) );	//si introduc in set noul vecin obtinut
			}
		}
		vizitat[curent] = true;
	}
}		
		

int main() {
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	
	int i, j, a, b, c;

	f>>n>>m;
	for(i=1; i<=m; i++) {
		f>>a>>b>>c;
		vecin[a].push_back(b);		//adaug indicele vecinului
		muchie[a].push_back(c);		//si in acelasi timp si lungimea muchiei
	}
	best[1] = 0;
	for(i=2; i<=n; i++) best[i] = inf, vizitat[i] = false;

	q.insert( make_pair(0, 1) );		//introduc nodul sursa in heap
	dijkstra();

	for(i=2; i<=n; i++) 
		if(best[i]==inf) g<<"0 ";
		else g<<best[i]<<" ";
	g<<"\n";


	return 0;
}