#include <stdio.h>
#define lson(x) ((x)*2)
#define rson(x) ((x)*2+1)
#define father(x) ((x)/2)
#define inf 500000000

struct NOD
       { int info,cost;
         struct NOD *urm;};
typedef struct NOD *Lista;

Lista A[50005];
int cost[50005],H[500005],l;

void shift(int n,int x)
{
     int son,i;
     do{
         son=0;
         if (lson(x)<=n) {son=lson(x);
                         if (rson(x)<=n && cost[rson(x)]<cost[lson(x)]) son = rson(x);
             if (cost[son]>cost[x]) son = 0;
             }
     if (son) {
              i = H[son];
              H[son] = H[x];
              H[x] = i;
              x = son;
              }
     }while (son);
}

void percolate(int x)
{
     int key = H[x];
     while (x>1 && H[x]<H[father(x)])
     {
           H[x] = H[father(x)];
           x = father(x);
     }
     H[x] = key;
}

void remove()
{
     H[1]=H[l];
     l--;
     shift(l,1);
}

void add(int x)
{
 l++;
 H[l] = x;
 percolate(l);
}    

void dijkstra()
{
     int x;
     Lista q;
     while (l)
     {
          x = H[1];
          remove();
          q = A[x];
          while (q!=NULL)
          {
                if (cost[q->info] > cost[x]+q->cost) {
                                                            cost[q->info] = cost[x]+q->cost;
                                                            add(q->info);
                                                            } 
          q = q->urm;
          }
     }
}     

int main()
{
 FILE *in=fopen("dijkstra.in","r");
 FILE *out=fopen("dijskstra.out","w");
 int n,m,x;
 Lista urm;
 fscanf(in,"%d%d",&n,&m);
 for (x=2;x<=n;x++) cost[x] = inf;
 for (;m;m--)
 {
     urm = new NOD;
     fscanf(in,"%d%d%d",&x,&urm->info,&urm->cost);
     urm->urm = A[x];
     A[x] = urm;
 }
 l++;
 H[l] = 1;
 dijkstra();
 
 for (x=2;x<=n;x++) if (cost[x]!=inf) fprintf(out,"%d ",cost[x]);
                    else fprintf(out,"0 ");    
}