#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];
int p[LIMITA];
vector<unsigned short int> v[LIMITA], cost[LIMITA];
priority_queue<NOD, vector<NOD>, cmp> pq, printq;
bool sel[LIMITA];
//ifstream fin("dijkstra.in");
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

void print_q () { // mai simplu
  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, nj;
  NOD nod;
  for (i = 2; i <= n; i++)
    d[i] = MARE; // Initializam distanta fata de sursa.
  d[s] = 0;
  nod.n = 1; nod.d = 0;
  pq.push(nod);
  while (not pq.empty()) { // Selectam cate un nod.
    nod = pq.top(); pq.pop(); //print_q();
    nmin = nod.n;
    if (not sel[nmin]) {
      sel[nmin] = true; // retinem nodul care ne da minimul [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();
            //p[nj] = nmin;
          }
        }
      }
    }
  }
}

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 ";
    else
      fout << d[i] << ' ';
  }
  /*
  for (int nc = 412; nc != 0; nc = p[nc])
    fout << nc << ' ';
  fout << '\n' << d[412];
  */
  return 0;
}