#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
//#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];

bool sel[LIMITA];
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <pair<int, int>> h; // -distanta, nod

/*
void showh() {
  if (not h.empty())
    for (int i = 0; i < h.size(); i++)
      cout << '(' << -h[i].first << ", " << h[i].second << ") ";
  cout << endl;
}
*/

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;
  h.push_back(make_pair(0, 1)); // Punem sursa in coada.
  while (not h.empty()) {
    nmin = h[0].second;  // Nodul cu distanta minima de la sursa.
    pop_heap(h.begin(), h.end()); h.pop_back();
    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.
          h.push_back(make_pair(-d[nv], nv));
        }
      }
    }
  }
}

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