#include "bits/stdc++.h" using namespace std; #define int long long int #define endl '\n' #define pii pair<int, int> template<const bool isWeighted> struct BridgeTree { int nodes; int edges; int dfsTime; vector<vector<int>> graph; vector<vector<vector<int>>> tree; vector<int> nodeCost; vector<vector<int>> edgeList; vector<bool> isBridge; vector<bool> visited; vector<int> arrivalTime; vector<int> par; BridgeTree(int n, int m) { nodes = n; edges = m; dfsTime = 0; int szn = n + 1; int szm = m + 1; int sznode = isWeighted ? 3 : 2; graph = vector<vector<int>>(szn); tree = vector<vector<vector<int>>>(szn); nodeCost = vector<int>(szn); edgeList = vector<vector<int>>(szm, vector<int>(sznode)); isBridge = vector<bool>(szm); visited = vector<bool>(szn); arrivalTime = vector<int>(szn); par = vector<int>(szn); iota(par.begin(), par.end(), 0); } void readNodeCost() { for (int i = 1; i <= nodes; i++) { cin >> nodeCost[i]; } } void readEdges() { for (int e = 1; e <= edges; e++) { for (int &x : edgeList[e]) { cin >> x; } } } int getAdjacent(int u, int e) { return edgeList[e][0] ^ edgeList[e][1] ^ u; } int findRep(int p) { return par[p] = (par[p] == p ? p : findRep(par[p])); } void marge(int u, int v) { int p = findRep(u); int q = findRep(v); par[q] = par[p]; } int findBridge(int u, int edge = -1) { visited[u] = true; arrivalTime[u] = ++dfsTime; int minimumArrivalTime = arrivalTime[u]; for (int nextEdge : graph[u]) { int v = getAdjacent(u, nextEdge); if (visited[v] == false) { minimumArrivalTime = min(minimumArrivalTime, findBridge(v, nextEdge)); } else if (edge != -1) { minimumArrivalTime = min(minimumArrivalTime, arrivalTime[v]); } } if (minimumArrivalTime == arrivalTime[u] and edge != -1) { isBridge[edge] = true; } else if (edge != -1) { marge(edgeList[edge][0], edgeList[edge][1]); } return minimumArrivalTime; } void buildBridgeTree() { for (int i = 1; i <= nodes; i++) { if (visited[i] == false) { findBridge(i); } } for (int e = 1; e <= edges; e++) { int p = findRep(edgeList[e][0]); int q = findRep(edgeList[e][1]); if (p ^ q) { tree[p].emplace_back(q, isWeighted ? edgeList[e][2] : 0); tree[q].emplace_back(p, isWeighted ? edgeList[e][2] : 0); } } } // Implement solution methods from here }; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.precision(12); bool FILEIO = 1; if (FILEIO and fopen("in.txt", "r")) { freopen("in.txt", "r", stdin); } int n, m; cin >> n >> m; BridgeTree<false> brigeTree(n, m); brigeTree.readNodeCost(); brigeTree.readEdges(); brigeTree.buildBridgeTree(); }