#include <iostream>
#include <vector>
#include <queue>
#include <limits>

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

typedef int                                             Node;     
typedef std::vector<std::vector<std::pair<Node, int>>>  List;

void relax(std::priority_queue<std::pair<int, Node>>& Q,
           std::vector<int>& distance, std::vector<Node>& pi,
           int u, int v, int w) 
{
    if (distance[v] > distance[u] + w) {
        distance[v] = distance[u] + w;
        Q.push(std::make_pair(distance[v], v));
        pi[v] = u;
    }
}

std::vector<int> init_distance(int s, int n)
{
    std::vector<int> distance(n, INF);
    distance[s] = 0;
    return distance;
}

std::vector<Node> init_pi(int n)
{
    std::vector<int> pi(n, -1);
    return pi;
}

void dijkstra(List& neighbours, std::vector<int>& distance,
              std::vector<Node>& pi, int s)
{
    distance = init_distance(s, neighbours.size());
    pi = init_pi(neighbours.size());

    std::priority_queue<std::pair<int, Node>> Q;
    Q.push(std::make_pair(distance[s], s));

    while (!Q.empty()) {
        Node u = Q.top().second; Q.pop();
        for (auto [v, w] : neighbours[u]) {
            relax(Q, distance, pi, u, v, w);
        }
    }
}

// baza u == v: u
// korak u~>v:u~>v.pi->v
bool print_path(std::vector<Node>& pi, int u, int v)
{
    if (u == v) {
        std::cout << u << " ";
        return true;
    } else {
        if (print_path(pi, u, pi[v])) {
            std::cout << v << " ";
            return true;
        }
    }
    return false;
}

int main(int argc, const char *argv[])
{
    List neighbours = {
        { {1, 10}, {3, 5} },
        { {2, 1}, {3, 2} },
        { {4, 4} },
        { {1, 3}, {2, 9}, {4, 2} },
        { {0, 7}, {2, 6} }
    };

    std::vector<int> distance;
    std::vector<int> pi;
    dijkstra(neighbours, distance, pi, 0);
    
    for (int i = 0; i < distance.size(); i++) {
        std::cout << i << ": " << distance[i] << std::endl;
    }

    for (int i = 1; i < pi.size(); i++) {
        std::cout << 0 << "->" << i << ": ";
        print_path(pi, 0, i);
        std::cout << std::endl;
    }
    
    return 0;
}