C++ Dijkstra/Prim's Algorithm O(EV^2)
\nstruct Edge{\n    int idx, to, cost;\n    Edge(int idx, int to, int cost) : idx(idx), to(to), cost(cost) {};\n\t// Operator is inverted to make priority_queue
```\nstruct Edge{\n    int idx, to, cost;\n    Edge(int idx, int to, int cost) : idx(idx), to(to), cost(cost) {};\n\t// Operator is inverted to make priority_queue a min heap\n    bool operator < (const Edge& other) const { return cost > other.cost; }\n};\n\nclass Solution {\npublic:\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        vector<vector<Edge>> adj(n);\n        for(int i = 0; i < edges.size(); i++){\n            adj[edges[i][0]].emplace_back(i, edges[i][1], edges[i][2]);\n            adj[edges[i][1]].emplace_back(i, edges[i][0], edges[i][2]);\n        }\n        int mn = prim(adj, -1, 0, -1); // Cost of MST on original graph\n        vector<vector<int>> ans(2);\n        for(int i = 0; i < edges.size(); i++){\n\t\t\t// Does force-taking this edge increase the MST cost? -> neither critical nor pseudo-critical\n            if(prim(adj, i, edges[i][0], -1) > mn) continue;\n\t\t\t// Does ignoring this edge increase the MST cost? -> critical if true, pseudo-critical if false\n            if(prim(adj, -1, 0, i) > mn) ans[0].push_back(i);\n            else ans[1].push_back(i);\n        }\n        return ans;\n    }\n    \n    int prim(vector<vector<Edge>>& adj, int startEdgeIdx, int startEdgeFrom, int ignoreEdgeIdx){\n        int cnt = 0, total = 0;\n        vector<bool> visited(adj.size());\n        priority_queue<Edge> pq;\n        pq.emplace(-1, startEdgeFrom, 0);\n        while(pq.size()){\n            auto [idx, to, cost] = pq.top();\n            pq.pop();\n            if(visited[to]) continue;\n            visited[to] = true;\n            cnt++;\n            total += cost;\n            if(cnt == adj.size()) break;\n            for(auto edge : adj[to]){\n                if(visited[edge.to] || edge.idx == ignoreEdgeIdx) continue;\n\t\t\t\t// If it\'s the start edge we assigned, we take the edge upfront and give it the highest priority by making it free\n                if(edge.idx == startEdgeIdx){\n                    total += edge.cost;\n                    edge.cost = 0;\n                }\n                pq.push(edge);\n            }\n        }\n        return cnt == adj.size() ? total : INT_MAX;\n    }\n};\n```
[]