#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

#define INF INT_MAX/2

#define NMAX 50000
#define MMAX 250000

struct arc{unsigned short a,b,c;};
arc v[MMAX];
unsigned short s[NMAX+1],start=1;
unsigned short pv[NMAX+1];
int d[NMAX+1];

void poz(int li,int ls,int&piv,arc e[]){
int i=li,j=ls,d=0;
arc t;
while(i<j){
	if(e[i].a>e[j].a){
		t=e[i];e[i]=e[j];e[j]=t;d=1-d;
		}
	i+=d;j-=1-d;
	}
piv=i;
}
void qsrt(int st,int dr,arc e[]){
int piv;
if(st<dr){
	poz(st,dr,piv,e);
	qsrt(st,piv-1,e);
	qsrt(piv+1,dr,e);
	}
}

int main(){
freopen("g1.in","r",stdin);
freopen("dijkstra.out","w",stdout);
int i,j,k,x,y,nrsel,gata;
int n,m;
int min;
unsigned short _x,_y,_z,pz;
scanf("%d%d\n",&n,&m);
for(i=1;i<=m;++i){
	scanf("%hu%hu%hu",&_x,&_y,&_z);
	v[i].a=_x,v[i].b=_y,v[i].c=_z;
	}
qsrt(1,m,v);
for(i=1;i<=m;++i){
	pz=v[i].a;
	if(!pv[pz]) pv[pz]=i;
	}

for(i=1;i<=n;++i) d[i]=INF;
d[1]=0;
i=pv[start];
if(i)
while(i<=m&&v[i].a==start){
	pz=v[i].b;
	d[pz]=v[i].c;
	++i;
	}

s[start]=1;
nrsel=1;gata=0;
int imin=2,ales,sum,umin=0;
do{
	 min=INF+INF;
	 ales=0;
	 for(i=imin;i<=n;++i)
		if(!s[i]){
			if(!ales) imin=i,ales=1;
			if(d[i]<min){
				min=d[i];k=i;
				if(umin==min) break;
				}
			}
	 umin=d[k];
	 nrsel++;
	 if(d[k]==INF||nrsel==n) gata=1;
	 else{
		s[k]=1;
		i=pv[k];
		if(i)
		while(i<=m&&v[i].a==k){
			pz=v[i].b;
			if(!s[pz]){
				sum=d[k]+v[i].c;
				if(d[pz]>sum) d[pz]=sum;
				}
			++i;
			}
		}
	 }while(!gata);

for(i=2;i<=n;++i)
	if(d[i]==INF) printf("0 ");
	else printf("%d ",d[i]);
return 0;
}