void relax(node& u, node& v, int cost){
    if(v.cost > u.cost + cost){
        v.cost = u.cost + cost;
        v.parent = u.index;
    }
}

void djikstra(graph& g, int start){
    priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > pq;
    for(int i = 0; i < g.nodes.size(); i++){
        g.nodes[i].cost = INF;
    }
    g.nodes[start].cost = 0;
    pq.push(mp(g.nodes[start].cost, start));
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        if(g.nodes[u].visited == false){
            g.nodes[u].visited = true;
            for(int i = 0; i < g.edges[u].size(); i++){
                int adj = g.edges[u][i].first;
                if(g.nodes[adj].visited == false){
                    relax(g.nodes[u], g.nodes[adj], g.edges[u][i].second);
                    pq.push(mp(g.nodes[adj].cost, adj));
                }
            }
        }
    }
}

void prim(graph& g, int start){
    priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > pq;
    for(int i = 0; i < g.nodes.size(); i++){
        g.nodes[i].cost = INF;
    }
    g.nodes[start].cost = 0;
    pq.push(mp(g.nodes[start].cost, start));
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        if(g.nodes[u].visited == false){
            g.nodes[u].visited = true;
            for(int i = 0; i < g.edges[u].size(); i++){
                int adj = g.edges[u][i].first;
                if(g.nodes[adj].visited == false && g.edges[u][i].second < g.nodes[adj].cost){
                    g.nodes[adj].cost = g.edges[u][i].second;
                    g.nodes[adj].parent = u;
                    pq.push(mp(g.nodes[adj].cost, adj));
                }
            }
        }
    }

}

void printMST(graph g){
    for (int i = 0; i < g.nodes.size(); ++i){
        if(g.nodes[i].parent != -1){
            cout << min(g.nodes[i].index + 1, g.nodes[i].parent + 1) << " "
                <<  max(g.nodes[i].index + 1, g.nodes[i].parent + 1)  << endl;
        }
    }
}