#include <bits/stdc++.h>

using namespace std;

const int Nmax = 50001;
const int INF = 2e9;
#define PII pair<int, int>

struct comp {
  bool operator()( pair<int, int> a, pair<int,int> b ) {
    if ( a.second < b.second )
      return false;
    return true;
 }
} ;
priority_queue< pair<int, int>, vector< pair<int, int> >, comp > q;
vector< PII > adj[Nmax];
int dist[Nmax];

int main()
{
    int n, m, i, u, v, w;
    ifstream fin ( "dijkstra.in" );
    ofstream fout ( "dijkstra.out" );

    fin >> n >> m;
    for ( i = 0; i < m; i ++ ) {
      fin >> u >> v >> w;
      adj[u].push_back( make_pair( v, w ) );
    }
    for ( i = 2; i <=n; i ++ )
      dist[ i ] = INF;
    q.push( {1,0} );
    while ( !q.empty() ) {
      u = q.top().first;
      for ( i = 0; i < adj[u].size(); i ++ ) {
        v = adj[u][i].first;
        w= adj[u][i].second;
        if ( dist[u] + w < dist[v] ) {
          dist [v] = dist[u] + w;
          q.push( {v, dist[v] } );
        }
      }
      q.pop();
    }

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

    return 0;
}