#include<fstream>
#include<vector>
using namespace std;
#define NMax 50005
const int INF = 2 << 29;

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

struct A{
	int vecin,cost;
};

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

void citire(){
	
	A aux;
	int x,vec;
	
	fin>>N>>M;
	
	for(int i=1;i<=M;i++){
		fin>>x>>aux.vecin>>aux.cost;
		if(aux.cost!=0)
			G[x].push_back(aux);
	}
	
	for(int i=1;i<=N;i++){
		key[i]=INF;
	}
	
	key[1]=0;
	viz[1]=1;
	for(int i=0;i<G[1].size();i++){
		vec=G[1][i].vecin;
		if( !viz[vec] && key[vec] > key[1] + G[1][i].cost)
			key[vec] = key[1] + G[1][i].cost;
	}
	
}

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

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

int main(){
	
	citire();
	solve();
	afisare();
	
	fin.close();
	fout.close();
	return 0;
}