#include <stdio.h>
#include <stdlib.h>
#define MAX 99999999
#define EEE 50001
typedef struct nod{
    long i,c;
    struct nod *urm;}NOD;
typedef struct hp{
    long long cost;
    long i;}heap;
long dheap,n,b[EEE];
long i,j,min;
long long minc,d[EEE];
int s[EEE];
heap h[EEE];
NOD *v[EEE],*p;

void citire()
 {   FILE *f;
 long i,x,y,m;
 long c;
    f=fopen("dijkstra.in","r");
    fscanf(f,"%ld %ld",&n,&m);
    for(i=0;i<=n;i++) { d[i]=MAX;
          if (i>1) {
               h[i-1].i=i;
               b[i]=i-1;} h[i].cost=MAX;
          }
    for(i=0;i<m;i++)
    {
        p=(NOD*)malloc(sizeof(NOD));
        fscanf(f,"%ld %ld %ld",&x,&y,&c);
        p->i=y; p->c=c; p->urm=v[x]; v[x]=p;
    }
    fclose(f);
}
void recon_heap(long i,heap a[])
{
    long l,r,maxim;
    heap aux;
    long aux1;
    l=i<<1;
    r=l+1;
    if ((r<=dheap)&&(a[r].cost<a[i].cost)) maxim=r;
              else maxim=i;
    if((l<=dheap)&&(a[l].cost<a[maxim].cost)) maxim=l;
    if (maxim!=i) {
         aux1=b[h[i].i];
              b[h[i].i]=b[h[maxim].i];
              b[h[maxim].i]=aux1;
              aux=a[maxim];
              a[maxim]=a[i];
              a[i]=aux;
              recon_heap(maxim,a);
                    }
}
void make_heap()
{
    long i;
    dheap=n-1;
  for(i=(dheap)/2;i>=1;i--) recon_heap(i,h);
}
void heapsort(heap a[])
{
    int i;
    for(i=0;i<n;i++)
    {
        printf(" %lld ",a[1].cost);
        a[1]=a[dheap];
        dheap--;
        recon_heap(1,h);
    }
}
void dec_key(long i,heap a[],long long key)
{
     heap aux;
     long aux1;
     a[i].cost=key;
     while ((i>1)&&(a[i/2].cost>a[i].cost))
      {   aux1=b[a[i].i];
      b[a[i].i]=b[a[i/2].i];
      b[a[i/2].i]=aux1;
          aux=a[i];
          a[i]=a[i/2];
          a[i/2]=aux;
          i=i/2;
      }
}

int main()
{  FILE *f;
long aux;
   citire();
   p=v[1];
   while (p)
    {
        d[p->i]=p->c;
        h[p->i-1].cost=p->c;
        p=p->urm;
    }
    s[1]=1;
    make_heap();
    d[1]=0;

    while (dheap)
    {
        minc=h[1].cost;
        aux=b[h[1].i];
        b[h[1].i]=b[h[dheap].i];
        b[h[dheap].i]=aux;
        min=h[1].i;
        h[1]=h[dheap]; dheap--;
        recon_heap(1,h);
        if(minc==MAX) break;
        p=v[min];
        while (p)
        {
            if ((d[p->i]>minc+p->c))
                             {
                                 d[p->i]=minc+p->c;
                                 dec_key(b[p->i],h,d[p->i]);
                             }
            p=p->urm;
        }
        s[min]=1;
    }
 f=fopen("dijkstra.out","w");
 for(i=2;i<=n;i++)
              if (d[i]!=MAX) fprintf(f,"%lld ",d[i]);
               else fprintf(f,"0 ");
 fclose(f);


 return 0;
}