#include<stdio.h>
#include<string.h>
#define N 50004
#define oo 0x3f3f3f3f
#define DIM 8192
FILE*f=fopen("dijkstra.in","r");
FILE*g=fopen("dijkstra.out","w");
struct nod{ int info,cost; nod *urm; };
nod *prim[N];
int n,m;
int D[N],viz[N],pz;
char ax[DIM];
void insert(int x, int y, int cst)
 {
 nod *p;
 p=new nod;
 p->info=y;
 p->cost=cst;
 p->urm=prim[x];
 prim[x]=p;
 }
void cit(int &x)
 {
  x=0;
  while(ax[pz]<'0' || ax[pz]>'9')

	if(++pz==DIM) fread(ax,1,DIM,f),pz=0;

	while(ax[pz]>='0' && ax[pz]<='9')
	{
	    x=x*10+ax[pz]-'0';
	    if(++pz==DIM)fread(ax, 1, DIM, f),pz=0;
	}
 }

void read()
 {
 cit(n);
 cit(m);
 int x,y,z;
 while(m--)
  {
  cit(x); cit(y); cit(z);
  insert(x,y,z);
  }
 }
void bellman()
 {
 int p,u,c[N],x,X=1;
 p=u=0;
 c[u]=1;
 memset(D,oo,sizeof(D));
 nod *q;
 D[1]=0;
 while(p<=u)
  {
  x=c[p];
  p=(p+1)%N;
  viz[x]=0;
  for(q=prim[x];q;q=q->urm)

   if(D[q->info] > D[x] + q->cost)
    {
    D[q->info] = D[x] + q->cost;
    if( viz[q->info] == 0)
     {
      u=(u+1)%N;
      c[u]=q->info;
      viz[q->info]=1;
     }
    }

  }
 int i;
 for(i=2;i<=n;++i) if(D[i]==oo) D[i]=0;
 for(i=2;i<=n;++i) fprintf(g,"%d ",D[i]);
 }
int main()
 {
 read();
 bellman();
 return 0;
 }