/* Dijkstra cu heapuri */
#include<stdio.h>
#include<string.h>
FILE*f=fopen("dijkstra.in","r");
FILE*g=fopen("dijkstra.out","w");
#define Nmax 50002
struct Graf
 {
 int vf, cst;
 Graf *urm;
 };
Graf *G[Nmax];
int H[Nmax]; //heapul. H[k] = nodul de pe pozitia k din heap
int poz[Nmax]; // poz[i] = pozitia in heap a nodului i
int k; //dimensiunea heapului
int d[Nmax];
int n,m;
void add(int x, int y, int cost) // muchia x->y cu costul cost
 {
 Graf *q;
 q=new Graf;
 q->vf=y;
 q->cst=cost;
 q->urm=G[x];
 G[x]=q;
 }
void read()
 {
 fscanf(f,"%d%d",&n,&m);
 int x,y,z;
 while(m--)
  {
  fscanf(f,"%d%d%d",&x,&y,&z);
  add(x,y,z);
  }
 }
void cerne(int x) // Duc in jos elementul de pe poz x in heap
 {
 int aux,F,T;
 T=x;
 do
  {
   F=0;
   if(2*T <= k) F=2*T;
   if(2*T+1 <= k && d[H[2*T+1]] <= d[H[F]]) F=2*T+1;
   if(d[F] >= d[T]) F=0;
   if(F)
    {
    aux=poz[H[F]] ; poz[H[F]] = poz[H[T]]; poz[H[T]] = aux;
    
    aux=H[F]; H[F]=H[T]; H[T]=aux;
    T=F;
    }
  }
 while(F);
 }
void update(int x) // urc nodul de pe pozitia x
 {
 int F;
 int aux;
 F=x;
 while(F>1)
  {
   if( d[H[F]] < d[H[F/2]] )
    {
    aux=poz[H[F]]; poz[H[F]]=poz[H[F/2]]; poz[H[F/2]]=aux;
    aux=H[F]; H[F]=H[F/2]; H[F/2]=aux;
    F=F/2;
    }
   else return;
  }
 }
void dijkstra()
 {
 int Inf=0x3f3f3f3f;
 int aux,i,pmin;
 Graf *q;
 for(i=2;i<=n;++i) d[i]=Inf;
 poz[1]=1;
 H[++k]=1;
 for(i=1;i<=n;++i)
  {
   pmin=H[1];
   aux=H[1]; H[1]=H[k]; H[k]=aux;
   --k;
   poz[H[1]] = 1;
   cerne(1);
   for(q=G[pmin];q;q=q->urm)
    {
    if(d[q->vf] > d[pmin]+q->cst)
     {
      d[q->vf]=d[pmin]+q->cst;

      if(poz[q->vf] != -1) update(poz[q->vf]);
      else
       {
       poz[q->vf]=++k;
       H[k]=q->vf;
       update(k);
       }

     }
    }
  }
 }
void print()
 {
 int i;
 int Inf=0x3f3f3f3f;
 for(i=2;i<=n;++i)
  fprintf(g,"%d ",d[i]==Inf ? 0:d[i]);
 }
int main()
 {
 read();
 memset(poz,-1, sizeof(poz));
 dijkstra();
 print();
 }