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

using namespace std;

const int N = 50001;

vector <pair <int, int> >G[N];
vector <bool> viz (N, 0);
vector <int> d(N, 0x3f3f3f3f);
set <pair <int, int> > s;



void dijkstra ( int sursa ){
    d[sursa] = 0;
    int aux;
    s.insert({sursa, 0});
    while ( !s.empty()){
      aux = (*s.begin()).first;
      s.erase ( s.begin() );
      if ( viz[aux] )
        continue;
      viz[aux] = true;
      for ( int i = 0; i < G[aux].size(); i++ )
        if ( not viz[G[aux][i].first] && d[aux] + G[aux][i].second < d[G[aux][i].first]){
          d[G[aux][i].first] = d[aux] + G[aux][i].second ;
          s.insert ( {G[aux][i].first,d[G[aux][i].first]} );
        }
    }
}

int main (){

  int n, 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 ( make_pair (y, cost) );
  }
  in.close();

  dijkstra ( 1 );

  //ofstream out ("date.out");
  ofstream out ("dijkstra.out");
  for ( i = 2; i <= n; i++ )
    out << d[i] - ( d[i] == -1) << " ";
  out.close();

  return 0;
}