#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int n, m;
struct elem {
  int nod, cost;
  bool operator<(const elem& b) const { return cost > b.cost; }
};
priority_queue<elem> q;
vector<elem> g[50005];
int d[50005];
int main() {
  ifstream cin("dijkstra.in");
  ofstream cout("dijkstra.out");
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int x, y, c;
    cin >> x >> y >> c;
    g[x].push_back({y, c});
  }
  for (int i = 1; i <= n; i++) d[i] = inf;
  d[1] = 0;
  q.push({1, 0});
  while (!q.empty()) {
    int nod = q.top().nod;
    int cost = q.top().cost;
    q.pop();
    if (cost != d[nod]) continue;
    for (elem i : g[nod])
      if (d[nod] + i.cost < d[i.nod]) {
        d[i.nod] = d[nod] + i.cost;
        q.push({i.nod, d[i.nod]});
      }
  }
  for (int i = 2; i <= n; i++)
    if (d[i] == inf)
      cout << 0 << " ";
    else
      cout << d[i] << " ";
  return 0;
}