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

#define MARE 100000000
#define LIMITA 50001

using namespace std;

struct NOD {
  int n, 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[1001];
vector<int> v[LIMITA], cost[LIMITA];
priority_queue<NOD, vector<NOD>, cmp> pq, printq;
bool sel[LIMITA], inq[LIMITA];
ifstream fin("dijkstra.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 minim, 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; // Aratam ca sursa este selectata.
  d[s] = 0; // Distanta de la sursa la sursa este 0.
  // Vecinii sursei
  for (i = 0; i <= v[1].size() - 1; i++) {
    nc = v[1][i]; d[nc] = cost[1][i];
    nod.n = nc; nod.d = d[nc];
    pq.push(nod);
    //print_q();
    inq[nc] = true;
  }
  for (i = 2; i <= n; i++) { // Selectam cate un nod.
    minim = MARE;
    nod = pq.top(); pq.pop();
    //print_q();
    nmin = nod.n; inq[nmin] = false; // retinem nodul care ne da minimul [nmin]
    /*
    if (not pq.empty())
      cout << "dimensiunea cozii = " << pq.size() << '\n';
      */
    sel[nmin] = true; // Includem nodul nmin in multimea nodurilor selectate. (Devine roz.)
    /*
    if (i == 5)
      cout << "v[nmin].size() = " << v[nmin].size();
      */
    //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
//      if (i == 5)
//        cout << "v[nmin].size() = " << v[nmin].size();
      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;   // actualizam distanta de la sursa la nod.
        if (not inq[nj]) {
          nod.n = nj; nod.d = d[nj];
          pq.push(nod);
          //print_q();
          inq[nj] = true;
        }
      }
//      cout << "Distantele :";
//      for (int k = 1; k <= n; k++) //
//        cout << d[k] << ' ';
//      cout << '\n';
    }
  }
}

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