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

using namespace std;

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

vector< pair<int, int> > G [N];
set< pair<int, int> >Set;
int d[N], n;
bool viz[N];

void init (){
  for ( int i = 1; i <= n; i++ )
    d[i] = INF;
}

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

void dijkstra (  ){
  int aux, i;
  d[1] = 0;
  Set.insert ( {0, 1} );
  while ( not Set.empty() ){
    aux = (*Set.begin()).second;
    Set.erase ( Set.begin());
    if ( viz[aux] == 1 )
      continue;
    viz[aux] = 1;
    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;
        Set.insert ({ d[G[aux][i].first], G[aux][i].first});
      }
  }
}

void afisare_date (){
  //ofstream out ("date.out");
  ofstream out ("dijkstra.out");
  for ( int i = 2; i <= n; ++i, out << " " )
    if ( d[i] == INF )
      out << 0;
    else out << d[i];
  out.close();

}

int main (){
  citire_date();
  dijkstra();
  afisare_date();
  return 0;
}