#include <bits/stdc++.h>
#include <stdio.h>

using namespace std;

template <class T>
class DijkstraGraph {
 public:
  DijkstraGraph(int num_vertices) : num_vertices_(num_vertices) {
    edges_.resize(num_vertices + 1);
  }

  void AddEdge(int to, int from, T cost) { edges_[to].push_back({from, cost}); }

  vector<T> GetDistances(int source) {
    vector<T> distance_(num_vertices_ + 1, kMaxInf);
    vector<bool> visited_(num_vertices_ + 1, 0);
    priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> q;

    distance_[source] = 0;
    q.push({0, source});

    while (!q.empty()) {
      int x = q.top().second;
      q.pop();

      if (visited_[x]) {
        continue;
      }
      visited_[x] = 1;

      for (auto it : edges_[x]) {
        int y = it.first;
        T cost = it.second;
        if (distance_[x] + cost < distance_[y]) {
          distance_[y] = distance_[x] + cost;
          q.push({distance_[y], y});
        }
      }
    }

    for (int i = 1; i <= num_vertices_; i++) {
      if (distance_[i] == kMaxInf) {
        distance_[i] = -1;
      }
    }

    return distance_;
  }

 private:
  static const int kMaxInf = numeric_limits<T>::max();
  const int num_vertices_;
  vector<vector<pair<int, T>>> edges_;
};

int main() {
  cin.sync_with_stdio(false);

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

  int n, m;
  cin >> n >> m;

  DijkstraGraph<int> dij(n);
  for (; m; m--) {
    int x, y, z;
    cin >> x >> y >> z;
    dij.AddEdge(x, y, z);
  }

  vector<int> ans = dij.GetDistances(1);
  for (int i = 2; i <= n; i++) {
    if (ans[i] == -1) {
      ans[i] = 0;
    }
    cout << ans[i] << " ";
  }

  return 0;
}