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

using namespace std;

struct solmu {
  int i, l;
};
struct ssort {
  bool operator()(const solmu &a, const solmu &b) const {
    if (a.l != b.l) return a.l > b.l;
    return a.i > b.i;
  }
};

int n, m;

vector<vector<solmu> > kaaret;
int pituudet[50001];

int main() {
  ifstream in("dijkstra.in", ifstream::in);
  in >> n >> m;
  for (int i = 0; i <= n; i++)
    pituudet[i] = -1;
  kaaret.resize(n+2);
  for (int i = 0; i < m; i++) {
    int a, b, l;
    in >> a >> b >> l;
    kaaret[a].push_back((solmu) {b, l});
    //cout << a << " " << b << " " << l << endl;
  }

  int kaydyt = 0;
  priority_queue<solmu, vector<solmu>, ssort> jono;
  jono.push((solmu){1, 0});
  //pituudet[1] = 0;
  while (kaydyt < n) {
    solmu s = jono.top(); jono.pop();
    //cout << "Ollaan: " << s.i <<" " << s.l << endl;
    if (pituudet[s.i] != -1)
      continue;
    kaydyt++;
    pituudet[s.i] = s.l;
    vector<solmu> seur = kaaret[s.i];
    for (vector<solmu>::iterator it = seur.begin(); it < seur.end(); it++) {
      jono.push((solmu) {it->i, s.l + it->l});
    }
  }

  for (int i = 0; i <= n; i++)
    if (pituudet[i] == -1)
      pituudet[i] = 0;
  ofstream out("dijkstra.out", ofstream::out);
  out << pituudet[2];
  for (int i = 3; i <= n; i++) {
    out << " " << pituudet[i];
  }
}