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

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

struct CostAndNode {
  int node;
  int cost;

  CostAndNode(int node, int cost) {
    this->node = node;
    this->cost = cost;
  }

  friend bool operator<(const CostAndNode& a, const CostAndNode& b) {
    return std::tie(a.cost, a.node) < std::tie(b.cost, b.node);
  }
};

class ShortestPathFinder {
public:
  explicit ShortestPathFinder(
      std::vector<std::vector<CostAndNode>> 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);

    std::priority_queue<CostAndNode> q;
    q.push(CostAndNode(source, 0));

    while (!q.empty()) {
      const auto front_elem = q.top();
      q.pop();

      if (front_elem.cost >= cost_to_node[front_elem.node]) {
        continue;
      }
      cost_to_node[front_elem.node] = front_elem.cost;

      for (const auto& elem : node_to_edges_[front_elem.node]) {
        int new_cost = elem.cost + front_elem.cost;
        q.push(CostAndNode(elem.node, new_cost));
      }
    }

    return cost_to_node;
  }

private:
  std::vector<std::vector<CostAndNode>> 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<CostAndNode>> graph(num_nodes, std::vector<CostAndNode>());
  for (int i = 0; i < num_edges; i++) {
    int start;
    int end;
    int cost;
    fin >> start >> end >> cost;
    graph[start - 1].push_back(CostAndNode(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;
}