#include<fstream.h>
#include<stdio.h>
long n,m;
struct nod {short cost;
			long nd;
			nod *adr;}v[50005];
long d[50005],tata[50005];
short al[50005];

int main()
{freopen("dijkstra.in","r",stdin);
 freopen("dijkstra.out","w",stdout);
 scanf("%ld%ld",&n,&m);
 long i,x,y;
 short c;
 nod *l;
 for(i=1;i<=m;i++)
	{scanf("%ld%ld%hd",&x,&y,&c);
	 if(v[x].nd==0)
		{v[x].nd=y;
		 v[x].cost=c;
		 v[x].adr=NULL;}
	 else
		{l=new nod;
		 l->nd=y;
		 l->cost=c;
		 l->adr=v[x].adr;
		 v[x].adr=l;
		 }
	 if(x==1) {d[y]=c;tata[y]=x;}
	}
 for(i=2;i<=n;i++)
	if(d[i]==0) d[i]=50000000;
 al[1]=1;
 long aux;
 short dmin;
 long next;
 for(aux=1;aux<n;aux++)
	{dmin=2000;
	 for(i=2;i<=n;i++)
		if(!al[i] && d[i]<dmin) {dmin=d[i];next=i;}
	 al[next]=1;
	 if(d[next]+v[next].cost<d[v[next].nd])
		d[v[next].nd]=d[next]+v[next].cost;
	 l=v[next].adr;
	 while(l!=NULL)
		{if(d[next]+l->cost<d[l->nd])
			d[l->nd]=d[next]+l->cost;
		 l=l->adr;
		}
	}
 for(i=2;i<=n;i++)
	if(d[i]<50000000) printf("%ld ",d[i]);
	else printf ("0 ");

 return 0;
}