#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

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

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

void init_dist () {
    for ( int node = 1; node <= NMAX; node ++ )
       dist[node] = INF;
}
void run_dijkstra ( int root ) {

    priority_queue <pair<int, int>> pq;
    pq.push ( { 0, root } );
    dist[root] = 0;

    while ( !pq.empty () ) {
       pair<int, int> best_edge = pq.top ();
       int best_node = best_edge.second;
       pq.pop ();

       if ( !visited[best_node] ) {
         visited[best_node] = true;
         for ( auto edge : graf[best_node] ) {
            if ( dist[best_node] + edge.first < dist[edge.second] ) {
              dist[edge.second] = dist[best_node] + edge.first;
              pq.push ( { -dist[edge.second], edge.second } );
            }
         }
       }
    }
}

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} );
   }

   init_dist ();
   run_dijkstra ( 1 );

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



    return 0;
}