#include <algorithm>
#include <fstream>
#include <limits>
#include <utility>
#include <vector>

#define INF std::numeric_limits<unsigned>::max()
#define COMP [](auto& lhs, auto& rhs) { return lhs.first > rhs.first; }

int main() {
  std::ifstream in("dijkstra.in");
  std::ofstream out("dijkstra.out");

  unsigned n, m;
  in >> n >> m;
  std::vector<std::vector<std::pair<unsigned, unsigned>>> graph;
  graph.reserve(n);
  for (unsigned i = 0; i < n; i++) graph.push_back(std::vector<std::pair<unsigned, unsigned>>());
  for (unsigned i = 0; i < m; i++) {
    unsigned from, to, cost;
    in >> from >> to >> cost;
    graph[from - 1].push_back(std::make_pair(cost, to));
  }

  std::vector<std::pair<unsigned, unsigned>> costs;
  costs.push_back(std::make_pair(0, 1));
  for (unsigned i = 1; i < n; i++) costs.push_back(std::make_pair(INF, i + 1));
  std::vector<unsigned> finalCosts;
  finalCosts.reserve(n);
  finalCosts.push_back(0);
  for (unsigned i = 1; i < n; i++) finalCosts.push_back(INF);
  std::vector<unsigned> positions;
  positions.reserve(n);
  for (unsigned i = 0; i < n; i++) positions.push_back(i);

  while (costs.size() != 0) {
    for (unsigned i = 0; i < costs.size(); i++) {
      positions[costs[i].second - 1] = i;
    }
    unsigned currentNode = costs.begin()->second;
    unsigned currentCost = finalCosts[currentNode - 1];
    for (auto v : graph[currentNode - 1]) {
      unsigned cost = v.first;
      unsigned node = v.second;
      finalCosts[node - 1] = std::min(finalCosts[node - 1], currentCost + cost);
      costs[positions[node - 1]].first = finalCosts[node - 1];
    }
    std::pop_heap(costs.begin(), costs.end(), COMP);
    costs.pop_back();
  }
  for (unsigned i = 1; i < n; i++) {
    if (finalCosts[i] == INF) finalCosts[i] = 0;
    out << finalCosts[i] << " ";
  }
  return 0;
}