#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

class Graph {
public:
    int n;
    // 인접 정점
    // first: 정점, second: 가중치
    vector<pii>* adj;

    Graph(int n) {
        this->n = n;
        adj = new vector<pii>[n];
    }

    // 간선 추가
    void insertEdge(int u, int v, int w) {
        this->adj[u].push_back(make_pair(v, w));
        this->adj[v].push_back(make_pair(u, w));
    }
};

class Compare {
public:
    // 우선순위 큐를 위한 비교 함수
    bool operator() (pii a, pii b) {
        return a.second > b.second;
    }
};

vector<int>* dijkstra(Graph* g, int start) {
    // 최단 거리가 발견되면 true
    vector<bool> found(g->n, false);

    // 해당 정점까지의 거리 (default : 무한)
    vector<int> distance(g->n, INT_MAX);

    // 최단거리가 업데이트 될때 바로 이전에 방문하게 되는 정점  
    vector<int>* from = new vector<int>(g->n);

    // 가장 가까운 정점을 찾기 위한 우선순위 큐
    // first: 정점 번호, second: 정점까지의 거리
    priority_queue<pii, vector<pii>, Compare> pq;

    // 출발지의 최단거리 발견
    found[start] = true;
    // 출발지까지 거리 0
    distance[start] = 0;

    // 우선순위 큐에 넣는다.
    pq.push(make_pair(start, 0));

    for (int i = 0; i < g->n; i++) {
        // 가장 가까운 정점을 우선순위 큐에서 꺼낸다.
        int u = pq.top().first;
        pq.pop();

        // 최단거리 발견
        found[u] = true;
        for (int j = 0; j < g->adj[u].size(); j++) {
            // 정점 u의 인접정점의 최단거리 업데이트
            pii v = g->adj[u][j];

            if (!found[v.first]) {
                if (distance[u] + v.second < distance[v.first]) {
                    distance[v.first] = distance[u] + v.second;
                    (*from)[v.first] = u;

                    // 우선순위 큐에 추가
                    pq.push(make_pair(v.first, distance[v.first]));
                }
            }
        }
    }

    return from;
}

// from[n]에서 목적지까지의 정점을 재귀적으로 출력한다.  
void trace_path(int s, int e, vector<int>* from) {
    // 기저 조건 : 시작점과 목적지가 같은 경우  
    if ((*from)[e] == s) {
        cout << s << " -> ";
        return;
    
    }

    // 재귀호출을 통해 정점 e전의 정점에 대한 경로를 출력한다..  
    trace_path(s, (*from)[e], from);
    
    // 최단경로에서 정점 e 바로 이전의 정점를 화면에 출력한다.  
    cout << (*from)[e] << " - > ";
}

// 마지막 목적지를 간편하게 화면의 출력하기 위해 함수 분리  
void print_path(int s, int e, vector<int>* from) {
    // 위의 trace_path를 호출하여 최단 경로를 출력한후,  
        trace_path(s, e, from);

    // 목적지의 정점 번호도 출력한다.  
    cout << e;
}


int main(void) {
    Graph* g = new Graph(7);
    g->insertEdge(0, 1, 7);
    g->insertEdge(1, 0, 7);
    g->insertEdge(0, 4, 3);
    g->insertEdge(4, 0, 3);
    g->insertEdge(0, 5, 10);
    g->insertEdge(5, 0, 10);
    g->insertEdge(1, 4, 2);
    g->insertEdge(4, 1, 2);
    g->insertEdge(1, 5, 6);
    g->insertEdge(5, 1, 6);
    g->insertEdge(1, 2, 4);
    g->insertEdge(2, 1, 4);
    g->insertEdge(1, 3, 10);
    g->insertEdge(3, 1, 10);
    g->insertEdge(2, 3, 2);
    g->insertEdge(3, 2, 2);
    g->insertEdge(4, 3, 11);
    g->insertEdge(3, 4, 11);
    g->insertEdge(4, 6, 5);
    g->insertEdge(6, 4, 5);
    g->insertEdge(6, 3, 4);
    g->insertEdge(3, 6, 4);
    g->insertEdge(3, 5, 9);
    g->insertEdge(5, 3, 9);


    // 최단 경로를 구한다.
    auto from = dijkstra(g, 0);

    // 0부터 각 정점까지의 경로 출력
    for (int i = 0; i < g->n; i++) {
        print_path(0, i, from);
        cout << "\n";
    }

    return 0;
}