# include <stdio.h>

# define FIN "dijkstra.in"
# define FOUT "dijkstra.out"
# define MAXN 50005
# define inf 1 << 20

struct pelem
{
   int info,cost;
   pelem *next;
};

int N,M,i,j,a,b,c,len,mini;
pelem *list[MAXN];
pelem *p;
int H[MAXN];
int D[MAXN];
int poz[MAXN];
    
    void down(int i,int n)
    {
         int tata,v,fiu;
         
         tata = i; fiu = i << 1; v = H[i];
         
         while (fiu <= n)
           {
               if (fiu < n)
                 if (D[H[fiu]]>D[H[fiu+1]]) fiu++;
               if (D[v]>D[H[fiu]])
                 {
                     H[tata] = H[fiu];
                     poz[H[tata]] = tata;
                     tata = fiu;
                     fiu = tata << 1;
                 }
               else fiu = n+1;
           }
         H[tata] = v;
         poz[v] = tata;
    }
    
    void up(int i,int n)
    {
         int tata,fiu,aux;
         
         fiu = i; tata = i >> 1;
         while (tata!=0 && D[H[tata]]>D[H[fiu]])
           {
               aux = H[fiu];
               H[fiu] = H[tata];
               poz[H[tata]] = fiu;
               H[tata] = aux;
               poz[aux] = tata;
               fiu = tata;
               tata = fiu >> 1;
           }
    }

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        
        scanf("%d%d",&N,&M);
        for (i = 1; i <= M; ++i)
          {
              scanf("%d%d%d",&a,&b,&c);
              p = new pelem;
              p->info = b;
              p->cost = c;
              p->next = list[a];
              list[a] = p;
          }
        
        for (i = 1; i <= N; ++i)
          {
              D[i] = inf;
              poz[i] = i;
              H[i] = i;
          }
        p = list[1];
        while (p != NULL)
          {
              D[p->info] = p->cost;
              p = p->next;
          }
          
        for (i = N >> 1; i >= 1; i--)
          down(i,N);
        
        for (i = N; i >= 1; i--)
          {
             mini =H[1];
             H[1] = H[i];
             down(1,i-1);
             p = list[mini];
             while (p != NULL)
               {
                   if (D[p->info]>D[mini]+p->cost)
                     {
                       D[p->info]=D[mini]+p->cost;
                       up(poz[p->info],i-1);
                     }
                   p = p->next;
               }
          }  
        
        for (i = 2; i <= N; ++i)
          if (D[i] == inf) printf("0 ");
            else printf("%d ",D[i]);
            
        return 0;
        
    }