#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;
bool sel[LIMITA];
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

void dijkstra (int s) {
  int nmin, dn, i, iv, nv;
  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); // Punem sursa in coada
  while (not pq.empty()) { // Selectam cate un nod.
    nod = pq.top(); pq.pop();
    nmin = nod.n;
    if (not sel[nmin]) {
      sel[nmin] = true; // retinem nodul care ne da minimul [nmin]
      for (iv = 0; iv < v[nmin].size(); iv++) { // doar vecinii lui nmin
        nv = v[nmin][iv]; // nodul vecin
        if (not sel[nv]) {
          dn = d[nmin] + cost[nmin][iv]; // calculam distanta noua, folosind nmin.
          if (d[nv] > dn) { // Daca am gasit un lant mai scurt prin nmin,
            d[nv] = dn;     // actualizam distanta de la sursa la nv.
            nod.n = nv; nod.d = d[nv]; pq.push(nod); // Punem nodul in coada.
          }
        }
      }
    }
  }
}

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] << ' ';
  }
  return 0;
}