#include 

using namespace std;

using pii = pair;

class Graph {
public:
    int n;
    //  
    // first: , second: 
    vector* adj;

    Graph(int n) {
        this->n = n;
        adj = new vector[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* dijkstra(Graph* g, int start) {
    //    true
    vector found(g->n, false);

    //    (default : )
    vector distance(g->n, INT_MAX);

    //          
    vector* from = new vector(g->n);

    //       
    // first:  , second:  
    priority_queue 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* from) {
    //   :      
    if ((*from)[e] == s) {
        cout 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