#include <bits/stdc++.h>

using namespace std;

int main() {
  freopen("dijkstra.in", "r", stdin);
  freopen("dijkstra.out", "w", stdout);
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  vector<int> d(n + 1, INT_MAX);
  d[1] = 0;
  vector<pair<int, int>> G[n + 1];
  for (int i = 1; i <= m; ++i) {
    int x, y, cost;
    cin >> x >> y >> cost;
    G[x].push_back({y, cost});
  }
  set<pair<int, int>> noduri;
  for (int i = 1; i <= n; ++i) {
    noduri.insert({d[i], i});
  }
  while (!noduri.empty()) {
    int c = (*(noduri.begin())).first, nod = (*(noduri.begin())).second;
    // cout << c << ' ' << nod << '\n';
    noduri.erase(noduri.begin());
    for (pair<int, int> k : G[nod]) {
      int nodv = k.first, cv = k.second;
      // cout << nodv << '\n';
      if (d[nodv] > (c > INT_MAX - cv ? INT_MAX : c + cv)) {
        // cout << noduri.erase({d[nodv], nodv}) << '\n';
        noduri.insert({c + cv, nodv});
        d[nodv] = c + cv;
      }
    }
  }
  for (int i = 2; i <= n; ++i) {
    cout << d[i] << ' ';
  }
  return 0;
}