struct node{
    int index, parent;
    double cost;
    bool visited;
    string color;
};

struct graph{
    vector<vector<pair<int, double> > > edges;
    vector<node> nodes;
    int V;
};

void init(graph& g, int n){
    g.V = n;
    g.nodes.resize(n);
    g.edges.resize(n);
    for (int i = 0; i < n; ++i){
        g.nodes[i].index = i;
        g.nodes[i].parent = -1;
        g.nodes[i].cost = 0;
        g.nodes[i].visited = false;
        g.nodes[i].color = "white";
    }
}

void dfs(graph& g, int n){
    g.nodes[n].visited = true;
    for (auto v : g.edges[n]){
        if(g.nodes[v].visited == false){
            dfs(g, v);
        }
    }
}

int bfs(graph& g, int n){
    vector<int> Q;
    int num_visited = 1;
    g.nodes[n].visited = true;
    Q.push_back(n);
    while(!Q.empty()){
        int current = Q.back();
        Q.pop_back();
        for (auto v : g.edges[current]){
            if(g.nodes[v].visited == false){
                g.nodes[v].visited = true;
                Q.push_back(v);
                num_visited++;
            }
        }
    }
    return num_visited;
}

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;
    vi dist(g.nodes.size());
    vi visited(g.nodes.size());
    for(int i = 0; i < g.nodes.size(); i++){
        dist[i] = INF;
        visited[i] = false;
    }
    dist[start] = 0;
    pq.push(mp(dist[start], start));
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        if(visited[u] == false){
            visited[u] = true;
            for(int i = 0; i < g.edges[u].size(); i++){
                int adj = g.edges[u][i].first;
                double w = g.edges[u][i].second;
                if(visited[adj] == false){
                    if(dist[adj] > dist[u] + w){
                        dist[adj] = dist[u] + w;
                        g.nodes[adj].parent = u;
                    }
                    pq.push(mp(dist[adj], adj));
                }
            }
        }
    }
}

void prim(graph& g, int start){
    priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > pq;
    vi dist(g.nodes.size());
    vi visited(g.nodes.size());
    for(int i = 0; i < g.nodes.size(); i++){
        dist[i] = INF;
        visited[i] = false;
    }
    dist[start] = 0;
    pq.push(mp(dist[start], start));
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        if(visited[u] == false){
            visited[u] = true;
            for(int i = 0; i < g.edges[u].size(); i++){
                int adj = g.edges[u][i].first;
                double w = g.edges[u][i].second;
                if(visited[adj] == false && w < dist[adj]){  // Diff from Djikstra
                    dist[adj] = w;
                    g.nodes[adj].parent = u;
                    pq.push(mp(dist[adj], 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;
        }
    }
}