#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

#define INF 0x3f3f3f3f
#define NMAX 50005
#define MMAX 250005
#define get_max(a,b) ((a)>(b)?(a):(b))
#define get_min(a,b) ((a)<(b)?(a):(b))

using namespace std;

ifstream in ( "dijkstra.in" );
ofstream out ( "dijkstra.out" );
vector < pair < int , int > > G[NMAX];
priority_queue < pair < int , int  > , vector < int , int > , greater < int , int > > Heap[NMAX];
int N , M  , Distance[NMAX];

int main ( void )
{
   in >> N >> M ;
   for ( int i = 1 ; i <= M ; ++i )
   {
      int x , y , cost ;
      in >> x >> y >> cost;
      G[x].push_back( make_pair ( y , cost ));
   }
   memset ( Distance , INF , sizeof ( Distance));
   Distance[1] = 0 ;
   Heap.push( make_pair ( 0 , 1 ));
   for ( ; !Heap.empty(); )
   {
      int cost , node ;
      node = Heap.top().second();
      cost = Heap.top().first;
      for ( vector < pair < int , int > > ::iterator it = G[node].begin() ; it != G[node].end() ; ++it )
      {
        if ( Distance[it->first] > cost +  it->second )
        {
        Distance [it->first ] = cost + it->second;
        Heap.push( make_pair ( Distance [it->first] , it->first ));
        }

      }
   }
   for ( int i = 2 ; i <= N ; ++i )
         out << ( Distance[i] == INF ? 0 : Distance[i] );
    in.close();
    out.close();
    return 0 ;
}