#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 *kaaret[50001];
int pituudet[50001];
int n, m;

int main() {
  ifstream in("dijkstra.in", ifstream::in);
  in >> n >> m;
  for (int i = 0; i <= n; i++) {
    kaaret[i] = new int[50001];
    pituudet[i] = 1 << 30;
  }
  //kaaret.resize(n+2);
  priority_queue<solmu, vector<solmu>, ssort> jono;

  for (int i = 0; i < m; i++) {
    int a, b, l;
    in >> a >> b >> l;
    kaaret[a][b] = l;
    if (a == 1) jono.push((solmu) {b, l});
  }

  int kaydyt = 0;
  pituudet[1] = 0;
  while (!jono.empty()) {
    solmu seur = jono.top(); jono.pop();
    if (pituudet[seur.i] > seur.l) {
      pituudet[seur.i] = seur.l;
      for (int i = 1; i <= n; i++) {
        if (kaaret[seur.i][i] && seur.i != i) jono.push((solmu) {i, seur.l + kaaret[seur.i][i]});
      }
    }
  }

  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];
  }
}