# include <stdio.h>
# include <vector>

using namespace std;

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

int N,M,i,j,a,b,c,len,mini;
vector <int> list[MAXN];
vector <int> cost[MAXN];
int H[MAXN];
int D[MAXN];
int poz[MAXN];
    
    void down(int i,int n)
    {
         int tata,v,fiu;
         
         tata = i; fiu = i*2; 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 * 2;
                 }
               else fiu = n+1;
           }
         H[tata] = v;
         poz[v] = tata;
    }
    
    void up(int i,int n)
    {
         int tata,fiu,aux;
         
         fiu = i; tata = i / 2;
         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 / 2;
           }
    }

    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);
              list[a].push_back(b);
              cost[a].push_back(c); 
          }
        
        for (i = 1; i <= N; ++i)
          {
              D[i] = inf;
              poz[i] = i;
              H[i] = i;
          }
        D[1] = (inf)+1;
        len = list[1].size();
        for (i = 0; i < len; i++)
          D[list[1][i]] = cost[1][i];
          
        for (i = N / 2; i >= 1; i--)
          down(i,N);
        
        i = N;
        while (i > 2)
          {
             mini =H[1];
             H[1] = H[i];
             i--;
             down(1,i);
             len = list[mini].size();
             for (j = 0; j < len; ++j)
               if (D[list[mini][j]]>D[mini]+cost[mini][j])
                 {
                    D[list[mini][j]]=D[mini]+cost[mini][j];
                    up(poz[list[mini][j]],i);
                 }
          }  
        
        for (i = 2; i <= N; ++i)
          if (D[i] == inf) printf("0 ");
            else printf("%d ",D[i]);
            
        return 0;
        
    }