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

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(to, cost));
  }

  std::vector<bool> visited;
  visited.reserve(n);
  for (unsigned i = 0; i < n; i++) visited.push_back(false);
  std::vector<std::pair<unsigned, unsigned>> costs;
  costs.reserve(n);
  costs.push_back(std::make_pair(1, 0));
  for (unsigned i = 1; i < n; i++) costs.push_back(std::make_pair(i + 1, std::numeric_limits<unsigned>::max()));

  unsigned numVisited = 0;
  while (numVisited < n) {
    unsigned index = 0;
    while (visited[index]) index++;
    auto current = costs[index];
    for (unsigned j = index; j < n; j++) {
      if (costs[j].second < current.second) {
        current = costs[j];
      }
    }
    visited[current.first - 1] = true;
    for (auto v : graph[current.first - 1]) {
      if (!visited[v.first - 1]) {
        costs[v.first - 1].second = std::min(current.second + v.second, costs[v.first - 1].second);
      }
    }
    numVisited++;
  }

  for (unsigned i = 1; i < n; i++) {
    if (costs[i].second == std::numeric_limits<unsigned>::max()) costs[i].second = 0;
    out << costs[i].second << " ";
  }
  return 0;
}