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

using namespace std;
const int NMAX = 5e4;
const int INF = 2e9;

int dist[1 + NMAX];
vector<pair<int, int>> graf[1 + NMAX];
bool visited[1 + NMAX];

void set_dist () {
    for ( int i = 1; i <= NMAX; i ++ )
       dist[i] = INF;
}

void run_dijkstra ( int root ) {
    set<pair<int, int>> pq;

    dist[root] = 0;
    pq.insert ( {0, 1} );

    while ( !pq.empty () ) {
       int best_node = pq.begin () -> second;
       pq.erase ( pq.begin () );

       if ( !visited[best_node] ) {
         visited[best_node] = true;

         for ( auto edge : graf[best_node] ) {
            int node = edge.second;
            int cost = edge.first;

            if ( dist[best_node] + cost < dist[node] ) {
              dist[node] = dist[best_node] + cost;
              pq.insert ( { dist[node], node } );
            }
         }
       }
    }
}

ifstream fin ( "dijkstra.in" );
ofstream fout ( "dijkstra.out" );
int main()
{
   int n, m; fin >> n >> m;
   for ( int i = 1; i <= m; i ++ ) {
      int x, y, cost; fin >> x >> y >> cost;
      graf[x].push_back ( {cost, y} );
   }

   set_dist ();
   run_dijkstra ( 1 );

   for ( int i = 2; i <= n; i ++ ) {

      if ( dist[i] == INF )
        fout << 0;
      else
        fout << dist[i];
      fout << ' ';
   }


    return 0;
}