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

#define INF INT_MAX/2

#define NMAX 50000
#define MMAX 250000

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

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);
	}
}
void refac(int vf,int nn){
int poz=vf,copil=2*vf,gata=0;
nod t=c[vf];
while(copil<=nn&&!gata){
	if(copil<nn&&c[copil].v>c[copil+1].v) ++copil;
	if(t.v>c[copil].v){
		c[poz]=c[copil];
		poz=copil;
		copil=2*poz;
		}
	else gata=1;
	}
c[poz]=t;
}
void init(){
int i;
for(i=nn/2;i>=2;--i) refac(i,nn);
}
void elim(){
c[1]=c[nn];
nn--;
refac(1,nn);
}

int main(){
freopen("g2.in","r",stdin);
freopen("dijkstra.out","w",stdout);
int i,k,nrsel,gata;
int n,m;
int min;
unsigned short _x,_y,_z,pz;
char sir[30],*p;
scanf("%d%d\n",&n,&m);
for(i=1;i<=m;++i){
	fgets(sir,29,stdin);
	p=sir;
	_x=atoi(p);
	while(*p!=32)++p;++p;
	_y=atoi(p);
	while(*p!=32)++p;++p;
	_z=atoi(p);
	while(*p!=32)++p;++p;
	//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;
	nn++;c[nn].v=d[pz];c[nn].p=pz;
	++i;
	}
init();
s[start]=1;
nrsel=1;gata=0;
int imin=2,ales,sum,umin=0;
nod aux;
do{
	 //min=INF+INF;
	 do{
		k=c[1].p;
		if(s[k]) elim();
		}while(s[k]);
	 elim();
	 /*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;
					nn++;c[nn].v=d[pz];c[nn].p=pz;
					init();
					}
				}
			++i;
			}
		}
	 }while(!gata);

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