#include <fstream>
#include <vector>
#include <set>
#define Nmax 50005
#define INF 1000000005

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector <int> ld[Nmax],lc[Nmax];
int dist[Nmax];
set <pair < int, int> > dij;
set <pair <int, int> > :: iterator w;
int n,m;
int i,c,ii;

int main()
{
  f >> n >> m;
     for ( ; m ; m-- )
      {int i,j,c;
          f >> i >> j >> c;
          ld[i].push_back(j);
          lc[i].push_back(c);
      }
    for ( int i = 2 ; i <= n ; i ++ )
     dist[i]=INF;

    dij.insert(make_pair(1,0));

    while( dij.empty() == 0 )
     {
       i = dij.begin() -> first;
       c = dij.begin() -> second;
      dij.erase( dij.begin() );
      for ( int k = 0 ; k < ld[i].size() ; k ++ )
       {
           ii = ld[i][k];
           if ( dist[i]+lc[i][k] < dist[ii] )
           {
              w = dij.find( make_pair( ii, dist[ii] ) );
              if (w != dij.end() )
                dij.erase(w);
              dist[ii] = dist[i]+lc[i][k];
              dij.insert(make_pair( ii , dist[ii]));
           }
       }

     }
    for ( int i = 2 ; i <= n ; i ++ )
      if( dist[i] == INF )
        g << "0 ";
      else
        g << dist[i] << " ";

}