#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> vecini[nmax];
int nr,m,drum[nmax],poz[nmax],h[nmax];
void citire(){
	int a;
	nod t;
	f>>nr>>m;
	for(int i=1;i<=m;i++){
		f>>a>>t.ind>>t.cost;
		vecini[a].push_back(t);
	}
}
void urca(int k){
	int key=h[k],t;
	while((k>1)&&(drum[key]<drum[h[k/2]])){
		t=k/2;
		swap(h[k],h[t]);
		poz[h[k]]=k;
		poz[h[t]]=t;
		k=t;
	}
}
void insert(int &n,int y,int unde){
	drum[unde]=y;
	h[++n]=unde;
	poz[unde]=n;
	urca(n);
}
void cerne(int n,int k){
	int fiu,fiud;
	do{
		fiu=0;
		if(fiu_stang(k)<=n){
			fiu=fiu_stang(k);
			fiud=fiu_drept(k);
			if(fiud<=n&&drum[h[fiud]]<drum[h[fiu]])
				fiu=fiud;
			if(drum[h[fiu]]>=drum[h[k]])
				fiu=0;
		}
		if(fiu!=0){
			swap(h[k],h[fiu]);
			poz[h[k]]=k;
			poz[h[fiu]]=fiu;
			k=fiu;
		}
	}
	while(fiu);
}
void dijkstra(){
	int n=0;
	for(int i=2;i<=nr;i++)
		drum[i]=inf;
	int minim,punct=0;
	insert(n,0,1);
	for(int i=1;i<=nr;i++){
		minim=drum[h[1]];
		punct=h[1];
		h[1]=h[n];
		n--;
		if(drum[h[1]]==inf)break;
		cerne(n,1);
		for(int j=0;j<vecini[punct].size();j++){
			int nou=vecini[punct][j].cost+minim;
			int indice=vecini[punct][j].ind;
			if(drum[indice]>nou)
				if(poz[indice]==0)
					insert(n,nou,indice);
				else{
					drum[indice]=nou;
					urca(poz[indice]);
				}
		}
	}
}
int main(){
	citire();
	dijkstra();
	for(int i=2;i<=nr;i++)
		if(drum[i]==inf)g<<"0 ";
	else
		g<<drum[i]<<" ";
	return 0;
}