#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << " = " << x << "\n";

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int inf = (int)1e9 + 7;
const int max_n = (int)5e4 + 5;

int n, m;

vector<pair<int, int>> g[max_n];

int d[max_n];

int main() {
  in >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, c;
    in >> u >> v >> c;
    g[u].emplace_back(v, c);
  }
  fill(d + 2, d + n + 1, inf);
  set<pair<int, int>> s;
  s.insert(make_pair(0, 1));
  while ((int)s.size() > 0) {
    pair<int, int> top = *s.begin();
    s.erase(top);
    int u = top.second, uCost = top.first;
    for (pair<int, int> e : g[u]) {
      int v = e.first, c = e.second;
      if (d[v] > uCost + c) {
        if (s.find(make_pair(d[v], v)) != s.end()) {
          s.erase(make_pair(d[v], v));
        }
        d[v] = uCost + c;
        s.insert(make_pair(d[v], v));
      }
    }
  }
  for (int i = 2; i <= n; i++) {
    if (d[i] == inf) {
      d[i] = 0;
    }
    out << d[i] << " ";
  }
  return 0;
}