#include <stdio.h>
#include <vector>
using namespace std;

const int nmax = 50001;
const int INF = 1 << 30;
vector<pair<int,int> > G[nmax];
pair<int,int> aux;
int N,M,k,d[nmax],viz[nmax],h[nmax],poz[nmax];


void read()       
     {freopen("dijkstra.in","r",stdin);
      int i,x,y,c;
      scanf("%d %d",&N,&M);
      for(i=1;i<=M;i++)
           {scanf("%d %d %d",&x,&y,&c);
            G[x].push_back(make_pair(y,c));
           }
      fclose(stdin);
      }
void swap(int x, int y)
{
    int t = h[x];
    h[x] = h[y];
    h[y] = t;
}

void push(int what)
{
    int tata;
    while ( what > 1 )
    {
        tata = what >> 1;

        if ( d[ h[tata] ] > d[ h[what] ] )
        {
            poz[ h[what] ] = tata;
            poz[ h[tata] ] = what;

            swap(tata, what);

            what = tata;
        }
        else
            what = 1;
    }
}

void pop(int what)
{
    int f;
    while ( what <= k )
    {
        f = what;
        if ( (what<<1) <= k )
        {
            f = what << 1;
            if ( f + 1 <= k )
                if ( d[ h[f + 1] ] < d[ h[f] ] )
                    ++f;
        }
        else
            return;

        if ( d[ h[what] ] > d[ h[f] ] )
        {
            poz[ h[what] ] = f;
            poz[ h[f] ] = what;

            swap(what, f);

            what = f;
        }
        else
            return;
    }
}
void dijkstra()
     {vector<pair<int,int> >::iterator it;
      int i,j,indmin;
     
      for(i=2;i<=N;i++)    {d[i]=INF;poz[i]=-1;}
      
      h[++k]=k;poz[k]=k;    //initializare heap
     
      while(k)
          {indmin=h[1];     //scoatere radacina
           swap(1,k);
           poz[h[1]]=1;
           k--;
           pop(1);
           
           
           for(j=0;j<G[indmin].size();j++)                     //parcurgere noduri vecine
                     if(d[G[indmin][j].first]>d[indmin]+G[indmin][j].second)
                                {d[G[indmin][j].first]=d[indmin]+G[indmin][j].second;
                                
                                 if(poz[G[indmin][j].first]!=-1)    push(poz[G[indmin][j].first]);   
                                 
                                 else                              {h[++k]=G[indmin][j].first;
                                                                    poz[h[k]]=k;
                                                                    push(k);
                                                                   }
                                }
           }  
      }
void write()
     {freopen("dijkstra.out","w",stdout);
      int i;
      for(i=2;i<=N;i++)   printf("%d ",d[i] == INF ? 0 : d[i]);
      printf("\n");
      fclose(stdout);
      }
int main()
    {read();
     dijkstra();
     write();
     return 0;
     }