#include <iostream>
#include <fstream>
#include <set>
#include <vector>

using namespace std;
const int N_MAX = 5e4;
const int M_MAX = 25e4;
const int INF = 2e9;

struct graf_edge {
      int cost, to;
};
vector<graf_edge> graf[1 + N_MAX];

int dist[1 + N_MAX];
int visited[1 + N_MAX];

void reset_dist () {
    for ( int i = 0; i <= N_MAX; i ++ )
       dist[i] = INF;
}

void run_dijkstra () {

    set<pair<int,int>> pq;
    dist[1] = 0;
    pq.insert ( {0, 1} );
    while ( !pq.empty () ) {
       pair<int, int> my_pair = (*pq.begin ());
       printf ( "%d\n", my_pair.first );
       int node = my_pair.second;

       pq.erase ( pq.begin () );


       if ( visited[node] == 0 ) {
         visited[node] = 1;
         for ( auto x : graf[node] ) {
            if ( dist[node] + x.cost < dist[x.to] ) {
              dist[x.to] = dist[node] + x.cost;
              pq.insert ( { dist[x.to], x.to } );
            }
         }
      }
    }

}
ifstream fin ( "dijkstra.in" );
ofstream fout ( "dijkstra.out" );

int main()
{
   int n, m; fin >> n >> m;
   for ( int i = 1; i <= m; i ++ ) {
      int a, b, x; fin >> a >> b >> x;
      graf[a].push_back ( {x, b} );
   }

   reset_dist ();
   run_dijkstra ();

   for ( int i = 2; i <= n; i ++ ) {
      if ( dist[i] == INF )
        fout << 0 << ' ';
      else
        fout << dist[i] << ' ';
   }



    return 0;
}