#include <fstream>
#include <string>
#include <queue>
#include <vector>
#include <climits>
#include <tuple>
#include <unordered_set>

const std::string kInputFileName = "dijkstra.in";
const std::string kOutputFileName = "dijkstra.out";

using NodeAndCost = std::pair<int, int>;

class ShortestPathFinder {
public:
  explicit ShortestPathFinder(
      std::vector<std::vector<NodeAndCost>> node_to_edges) :
    node_to_edges_(std::move(node_to_edges)) {}

  std::vector<int> FindShortestPathsFromNode(int source) {
    std::vector<int> cost_to_node(node_to_edges_.size(), INT_MAX);
    cost_to_node[source] = 0;

    std::priority_queue<NodeAndCost, std::vector<NodeAndCost>, 
      std::greater<NodeAndCost>> q;
    q.push({0, source});

    std::unordered_set<int> visited;

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

      if (visited.count(current_node)) {
        continue;
      }
      visited.insert(current_node);

      for (const auto& edge : node_to_edges_[current_node]) {
        int neighbor = edge.first;
        int cost = edge.second;
        int new_cost = cost + cost_to_node[current_node];
        if (new_cost < cost_to_node[neighbor]) {
          cost_to_node[neighbor] = new_cost;
          q.push({new_cost, neighbor});
        }
      }
    }

    return cost_to_node;
  }

private:
  std::vector<std::vector<NodeAndCost>> node_to_edges_;
};

int main() {
  std::ifstream fin(kInputFileName);
  std::ofstream fout(kOutputFileName);

  int num_nodes;
  fin >> num_nodes;

  int num_edges;
  fin >> num_edges;

  std::vector<std::vector<NodeAndCost>> graph(num_nodes, std::vector<NodeAndCost>());
  for (int i = 0; i < num_edges; i++) {
    int start;
    int end;
    int cost;
    fin >> start >> end >> cost;
    graph[start - 1].push_back({end - 1, cost});
  }

  ShortestPathFinder finder(std::move(graph));

  std::vector<int> shortest_paths = finder.FindShortestPathsFromNode(0);

  for (int i = 1; i < shortest_paths.size(); i++) {
    fout << (shortest_paths[i] == INT_MAX ? 0 : shortest_paths[i]) << ' ';
  }

  return 0;
}