#include <stdio.h>
#include <iostream>
#define inf 2000000000
using namespace std;

FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");

struct nod {int info,cost; nod *urm;};
nod *prim[50001];
int n,m;

void add(nod *&prim, int x, int y)
{  nod *p=new nod;
   p->info=x; p->cost=y; p->urm=prim; prim=p;
}

void Citire()
{ int i,x,y,cost;
  fscanf(f,"%d%d",&n,&m);
  for(i=1;i<=m;i++)
     { fscanf(f,"%d%d%d",&x,&y,&cost);
       add(prim[x],y,cost);
     }
}

void Dijskstra()
{  int viz[50001]={0},d[50001],i,j,distmin,x;
   nod *p;
   for(i=1;i<=n;i++) d[i]=inf;
   for(p=prim[1];p;p=p->urm)
       d[p->info]=p->cost;
   viz[1]=1; d[1]=0;
   for(i=1;i<=n-1;i++)
     { distmin=inf+1;
       for(j=1;j<=n;j++)
          if(viz[j]==0 && d[j]<distmin)
              {distmin=d[j]; x=j;}
       viz[x]=1;
       for(p=prim[x];p;p=p->urm)
           if(viz[p->info]==0)
               if(d[x]+p->cost<d[p->info])
                    d[p->info]=d[x]+p->cost;
     }
   for(i=2;i<=n;i++)
     if(d[i]==inf) fprintf(g,"%d ",0);
     else fprintf(g,"%d ",d[i]);
}

int main()
{
    Citire();
    Dijskstra();
    return 0;
}