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

#define INF std::numeric_limits<unsigned>::max()

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::set<std::pair<unsigned, unsigned>> costs;
  costs.insert(std::make_pair(0, 1));
  for (unsigned i = 1; i < n; i++) costs.insert(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);

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