#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[50005],l,pc[50005];

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 N)
{
     int x;
     Lista q;
     for (;l;)
     {
          x = H[1];
          remove();
          
          if (pc[x]>cost[x]) 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()
{
 freopen("dijkstra.in","r",stdin);
 freopen("dijkstra.out","w",stdout);
 int n,m,x;
 Lista urm;
 scanf("%d%d",&n,&m);
 for (x=2;x<=n;x++) {cost[x] = inf;
                     pc[x] = inf+1;
                     }
                     pc[1] = inf+1;
 for (;m;m--)
 {
     urm = new NOD;
     scanf("%d%d%d",&x,&urm->info,&urm->cost);
     urm->urm = A[x];
     A[x] = urm;
 }
 l++;
 H[l] = 1;
 dijkstra(n);
 
 for (x=2;x<=n;x++) if (cost[x]!=inf) printf("%d ",cost[x]);
                    else printf("0 ");    
}