#include <bits/stdc++.h>
using namespace std;

#define INF (INT_MAX / 2)

int main() {
  ifstream fin("dijkstra.in");
  ofstream fout("dijkstra.out");

  int n, m;
  fin >> n >> m;

  vector<vector<pair<int, int>>> adj(n);
  for (int i = 0, x, y, c; i < m; ++i) {
    fin >> x >> y >> c;
    adj[x - 1].push_back({y - 1, c});
  }

  vector<int> dist(n, INF);
  priority_queue<pair<int, int>> pq;

  pq.push({0, 0});
  dist[0] = 0;

  while (!pq.empty()) {
    auto [d, c] = pq.top();
    pq.pop();

    d = -d;

    if (d != dist[c])
      continue;

    for (auto [neigh, cost] : adj[c])
      if (d + cost < dist[neigh]) {
        dist[neigh] = d + cost;
        pq.push({-(d + cost), neigh});
      }
  }

  for (int i = 1; i < n; ++i)
    fout << (dist[i] == INF ? -1 : dist[i]) << ' ';
  fout << '\n';
}