#include <iostream>
#include <queue>
#include <set>
#include <vector>

struct Edge {
  int Vertex = 0;
  int Weight = 0;
};

std::pair<std::vector<int>, std::vector<int>> Dijkstra(const std::vector<std::vector<Edge>>& graph, int start) {
  auto result = std::make_pair(std::vector(graph.size(), std::numeric_limits<int>::max()),
                               std::vector(graph.size(), -1));
  auto& distance = result.first;
  auto& prev = result.second;
  // Для каждой вершины: расстояние и номер вершины
  std::set<std::pair<int, int>> q;
//  std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> q;
  q.insert({0, start});
  distance[start] = 0;
  while (!q.empty()) {
    auto it = q.begin();
    int u = it->second;
    q.erase(it);

    for (auto e : graph[u]) {
      int v = e.Vertex;
      if (distance[u] + e.Weight < distance[v]) {
        auto itv = q.find({distance[v], v});
        if (itv != q.end()) q.erase(itv);

        distance[v] = distance[u] + e.Weight;
        prev[v] = u;
        q.insert({distance[v], v});
      }
    }
  }
  return result;
}

/*
7
10
1 6 14
1 3 9
1 2 7
2 3 10
3 6 2
6 5 9
2 4 15
3 4 11
4 5 6
5 4 6
*/

int main1() {
  int n = 0; std::cin >> n;
  // Для каждой вершины храним пару
  std::vector<std::vector<Edge>> graph(n);
  int edges_count = 0; std::cin >> edges_count;
  for (int i = 0; i < edges_count; ++i) {
    int u, v, weight; std::cin >> u >> v >> weight;
    graph[u].push_back({v, weight});
  }

  auto [d, prev] = Dijkstra(graph, 1);
  for (int value : d) std::cout << value << " ";
  std::cout << std::endl;
  for (int value : prev) std::cout << value << " ";
  std::cout << std::endl;
  return 0;
}

class DSU {
 public:
  explicit DSU(size_t n) : parent(n) {
    for (int i = 0; i < n; ++i) parent[i] = i;
  }
  int Find(int v) {
    return (parent[v] == v) ? v : (parent[v] = Find(parent[v]));
  }
  void Union(int u, int v) {
    parent[v] = u;
  }
 private:
  std::vector<int> parent;
};

int main() {

}