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

using namespace std;

const int N = 50001;
const int INF = 0x3f3f3f3f;

vector <pair <int, int> >G[N];
priority_queue <pair <int, int> >P;
vector <int> d(N, INF);
bool viz[N];

int main (){

  int n, m, aux, i, x, y, cost;

  ifstream in ("dijkstra.in");
  in >> n >> m;
  for ( i = 0; i < m; ++i ){
    in >> x >> y >> cost;
    G[x].push_back(make_pair(y, cost));
  }
  in.close();

  d[1] = 0;
  P.push ( {0, 1} );
  while ( not P.empty()){
    aux = P.top().second;
    P.pop();
    if ( viz[aux] )
      continue;
    viz[aux] = true;
    for ( i = 0; i < G[aux].size(); ++i )
      if ( not viz[G[aux][i].first] && d[G[aux][i].first] > d[aux] + G[aux][i].second ){
        d[G[aux][i].first] = d[aux] + G[aux][i].second;
        P.push({ d[G[aux][i].first], G[aux][i].first});
      }
  }

  ofstream out ("dijkstra.out");
  for ( i = 2; i <= n; ++i, out << " " )
    out << ( d[i] == INF ? 0 : d[i] );
  out.close();

  return 0;
}