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

#define MARE 100000000
#define LIMITA 50001

using namespace std;

struct NOD {
  unsigned short int n;
  int d;
};

struct cmp {
  bool operator()(const NOD& a, const NOD& b) const {
    return (a.d > b.d); // descrescator
  }
};

int i, n, m, x, y, c, s, d[LIMITA];
vector<unsigned short int> v[LIMITA], cost[LIMITA];
priority_queue<NOD, vector<NOD>, cmp> pq, printq;
bool sel[LIMITA];
ifstream fin("d4.in");
ofstream fout("dijkstra.out");

void print_q () {
  vector<NOD> qt;
  vector<NOD>::iterator it;
  NOD nc;
  while (not pq.empty()) {
    nc = pq.top();
    qt.push_back(nc);
    pq.pop();
  }
  for (it = qt.begin(); it != qt.end(); it++) {
    cout << (*it).n << ' ';
    pq.push(*it);
  }
  cout << '\n';
}

void dijkstra (int s) {
  int nmin, dn, i, j, nc, nj;
  NOD nod;
  for (i = 2; i <= n; i++)
    d[i] = MARE; // Initializam distanta fata de sursa.
  sel[s] = true; d[s] = 0;
  nod.n = 1; nod.d = 0;
  pq.push(nod);
  for (i = 1; i <= n; i++) { // Selectam cate un nod.
    nod = pq.top(); pq.pop(); //print_q();
    nmin = nod.n; sel[nmin] = true; // retinem nodul care ne da minimul [nmin]
    //for (j = 0; j <= v[nmin].size() - 1; j++) { !! // doar vecinii lui nmin
    for (j = 0; j < v[nmin].size(); j++) { // doar vecinii lui nmin
      nj = v[nmin][j];
      if (not sel[nj]) {      // neselectat,
        dn = d[nmin] + cost[nmin][j]; // calculam distanta noua, folosind nmin.
        if (d[nj] > dn) { // Daca am gasit un lant mai scurt prin nmin,
          d[nj] = dn; nod.n = nj; nod.d = d[nj]; pq.push(nod); //print_q();
        }
      }
    }
  }
}

int main () {
  fin >> n >> m;
  for (i = 1; i <= m; i++) {
    fin >> x >> y;
    v[x].push_back(y); // vectori de vecini
    fin >> c;
    cost[x].push_back(c);
  }
  dijkstra(1);
  for (i = 2; i <= n; i++) {
    if (d[i] == MARE)
      fout << "0\n";
    else
      fout << d[i] << '\n';
  }
  return 0;
}