#include<fstream>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#define NMax 50003
#define INF 999999999

typedef unsigned int uint;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct A{
	int vec;
	int cost;
};

int N,M,key[NMax],Heap[NMax],viz[NMax],Poz[NMax];
vector<A> G[NMax];

void read(){
	fin>>N>>M;
	
	A aux;
	int x,y,c;
	for(int i=1;i<=M;i++){
		fin>>x>>y>>c;
		aux.vec=y,aux.cost=c;
		if(aux.cost==0)
			aux.cost=INF;
		G[x].push_back(aux);
	}
	
}

void move_up(int X){
	
	while(X/2 && key[Heap[X]]<key[Heap[X/2]]){
		swap(Heap[X],Heap[X/2]);
		Poz[Heap[X]]=X;
		Poz[Heap[X/2]]=X/2;
		X/=2;
	}
	
}

void move_down(int X, int LIM){
	int Y=0;
	while(X!=Y){
		Y=X;
		
		if( 2*Y <= LIM && key[Heap[X]] > key[Heap[2*Y]] ) X=2*Y;
		if( 2*Y+1 <= LIM && key[Heap[X]] > key[Heap[2*Y+1]] ) X=2*Y+1;
		
		swap(Heap[X],Heap[Y]);
		Poz[Heap[X]]=X;
		Poz[Heap[Y]]=Y;
		
	}
}

void solve(){
	
	int Nr,Vf;
	
	for(int i=1;i<=N;i++){
		key[i]=INF;
		Heap[i]=i;
		Poz[i]=i;
	}
	
	key[1]=0;
	Nr=N;
	
	while(Nr){
		
		Vf=Heap[1];
		viz[Vf]=1;
		Heap[1]=Heap[Nr];
		Poz[Heap[Nr--]]=1;
		move_down(1,Nr);
		
		for(uint i=0;i<G[Vf].size();i++){
			if(!viz[G[Vf][i].vec] && key[G[Vf][i].vec]>key[Vf]+G[Vf][i].cost ){
				key[G[Vf][i].vec] = key[Vf] + G[Vf][i].cost;
				move_up(Poz[G[Vf][i].vec]);
			}
		}
		
	}
	
}

void show(){
	
	for(int i=2;i<=N;i++){
		if(key[i]==INF)
			fout<<"0 ";
		else
			fout<<key[i]<<" ";
	}
	fout<<"\n";
	
}

int main(){
	
	read();
	solve();
	show();
	
	/*fout<<N<<"\n";
	for(int i=1;i<=N;i++){
		fout<<G[i].size()<<" ";
	}*/
	
	fin.close();
	fout.close();
	
	return 0;
}