#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+1];
nod c[NMAX*2],nnul;
unsigned short s[NMAX+1],start=1;
int 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 nou(){
int copil=nn,parinte=nn/2;
nod t;
while(parinte>=1&&c[parinte].v>c[copil].v){
	t=c[copil];c[copil]=c[parinte];c[parinte]=t;
	copil=parinte;
	parinte=copil/2;
	}
}
void init(){
int i;
for(i=nn/2;i>=1;--i) refac(i,nn);
}
void elim(){
if(nn){
	c[1]=c[nn];
	--nn;
	refac(1,nn);
	}
else c[1]=nnul;
}

int main(){
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
int i,k,nrsel,gata;
int n,m;
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);
	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 sum;
do{
	 do{
		k=c[1].p;
		if(s[k]) elim();
		}while(s[k]&&k);
	 if(k) elim();
	 else break;

	 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;
					while(s[c[nn].p]) nn--;
					nn++;c[nn].v=d[pz];c[nn].p=pz;
					nou();
					}
				}
			++i;
			}
		}
	 }while(!gata);

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