#include<iostream>
#include<fstream>
#include<vector>
#define fiu_stang(k) (k<<1)
#define fiu_drept(k) ((k<<1)+1)
#define nmax 50001
#define inf 0xfffffff
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct nod{
	int ind,cost;
};
vector <nod> muchii[nmax];
int n,m,dist[nmax],poz[nmax],heap[nmax];
void citire(){
	int a;
	nod t;
	f>>n>>m;
	for(int i=1;i<=m;i++){
		f>>a>>t.ind>>t.cost;
		muchii[a].push_back(t);
	}
}
void urca(int k){
	int key=heap[k],t;
	while((k>1)&&(dist[key]<dist[heap[k/2]])){
		t=k/2;
		swap(heap[k],heap[t]);
		poz[heap[k]]=k;
		poz[heap[t]]=t;
		k=t;
	}
}
void insert(int &nr,int y,int unde){
	dist[unde]=y;
	heap[++nr]=unde;
	poz[unde]=nr;
	urca(nr);
}
void cerne(int nr,int k){
	int fiu,fiud;
	do{
		fiu=0;
		if(fiu_stang(k)<=nr){
			fiu=fiu_stang(k);
			fiud=fiu_drept(k);
			if(fiud<=nr&&dist[heap[fiud]]<dist[heap[fiu]])
				fiu=fiud;
			if(dist[heap[fiu]]>=dist[heap[k]])
				fiu=0;
		}
		if(fiu!=0){
			swap(heap[k],heap[fiu]);
			poz[heap[k]]=k;
			poz[heap[fiu]]=fiu;
			k=fiu;
		}
	}
	while(fiu);
}
void dijkstra(){
	int nr=0;
	for(int i=2;i<=n;i++)
		dist[i]=inf;
	int minim,punct=0;
	insert(nr,0,1);
	for(int i=1;i<=n;i++){
		minim=dist[heap[1]];
		punct=heap[1];
		heap[1]=heap[nr];
		nr--;
		if(dist[heap[1]]==inf)break;
		cerne(nr,1);
		for(int j=0;j<muchii[punct].size();j++){
			int nou=muchii[punct][j].cost+minim;
			int indice=muchii[punct][j].ind;
			if(dist[indice]>nou)
				if(poz[indice]==0)
					insert(nr,nou,indice);
				else{
					dist[indice]=nou;
					urca(poz[indice]);
				}
		}
	}
}
int main(){
	citire();
	dijkstra();
	for(int i=2;i<=n;i++)
		if(dist[i]==inf)g<<"0 ";
	else
		g<<dist[i]<<" ";
	return 0;
}