#include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; const int MAXN = 100005; const int MAXM = 300005; const int MAXK = 25; struct Edge { int u, v, w; }; bool compareEdges(const Edge& a, const Edge& b) { return a.w < b.w; } int N, M, K; Edge old_edges[MAXM]; pair<int, int> new_roads[MAXK]; int p_count[MAXN]; struct DSU { int parent[MAXN]; void init(int n) { for (int i = 0; i <= n; i++) parent[i] = i; } int find(int i) { if (parent[i] == i) return i; return parent[i] = find(parent[i]); } bool unite(int i, int j) { int root_i = find(i), root_j = find(j); if (root_i != root_j) { parent[root_i] = root_j; return true; } return false; } } dsu, dsu_super; int super_node[MAXN], mapping[MAXN], v_cnt; ll super_people[MAXK * 2]; vector<Edge> reduced_old; struct GraphEdge { int to, weight, id; }; vector<GraphEdge> adj[MAXK * 2]; ll subtree_people[MAXK * 2]; int edge_fees[MAXK]; // Tính tổng dân số trong cây con của đồ thị nén void get_subtree_people(int u, int p) { subtree_people[u] = super_people[u]; for (size_t i = 0; i < adj[u].size(); ++i) { if (adj[u][i].to == p) continue; get_subtree_people(adj[u][i].to, u); subtree_people[u] += subtree_people[adj[u][i].to]; } } // Tìm đường đi và cập nhật phí cầu đường tối đa cho cạnh của Mr Greedy bool update_path(int u, int target, int p, int w_limit) { if (u == target) return true; for (size_t i = 0; i < adj[u].size(); ++i) { if (adj[u][i].to == p) continue; if (update_path(adj[u][i].to, target, u, w_limit)) { if (adj[u][i].id >= 0) edge_fees[adj[u][i].id] = min(edge_fees[adj[u][i].id], w_limit); return true; } } return false; } // Tính tổng doanh thu cho mask hiện tại ll calculate_revenue(int u, int p) { ll res = 0; for (size_t i = 0; i < adj[u].size(); ++i) { if (adj[u][i].to == p) continue; if (adj[u][i].id >= 0) res += (ll)subtree_people[adj[u][i].to] * edge_fees[adj[u][i].id]; res += calculate_revenue(adj[u][i].to, u); } return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); if (!(cin >> N >> M >> K)) return 0; for (int i = 0; i < M; i++) cin >> old_edges[i].u >> old_edges[i].v >> old_edges[i].w; sort(old_edges, old_edges + M, compareEdges); for (int i = 0; i < K; i++) cin >> new_roads[i].first >> new_roads[i].second; for (int i = 1; i <= N; i++) cin >> p_count[i]; // Tìm MST cơ bản dsu.init(N); vector<Edge> mst_all; for (int i = 0; i < M; i++) if (dsu.unite(old_edges[i].u, old_edges[i].v)) mst_all.push_back(old_edges[i]); // Xác định các siêu đỉnh (nén đồ thị) dsu.init(N); for (int i = 0; i < K; i++) dsu.unite(new_roads[i].first, new_roads[i].second); dsu_super.init(N); for (size_t i = 0; i < mst_all.size(); ++i) { if (dsu.unite(mst_all[i].u, mst_all[i].v)) dsu_super.unite(mst_all[i].u, mst_all[i].v); else reduced_old.push_back(mst_all[i]); } memset(mapping, -1, sizeof(mapping)); v_cnt = 0; for (int i = 1; i <= N; i++) { int r = dsu_super.find(i); if (mapping[r] == -1) mapping[r] = v_cnt++; super_node[i] = mapping[r]; super_people[super_node[i]] += p_count[i]; } ll max_rev = 0; // Duyệt tất cả các tập con cạnh mới (2^K) for (int mask = 1; mask < (1 << K); mask++) { dsu.init(v_cnt); bool cycle = false; for (int i = 0; i < v_cnt; i++) adj[i].clear(); for (int i = 0; i < K; i++) if ((mask >> i) & 1) { int u = super_node[new_roads[i].first], v = super_node[new_roads[i].second]; if (!dsu.unite(u, v)) { cycle = true; break; } adj[u].push_back({v, 0, i}); adj[v].push_back({u, 0, i}); } if (cycle) continue; vector<Edge> unused; for (size_t i = 0; i < reduced_old.size(); ++i) { int u = super_node[reduced_old[i].u], v = super_node[reduced_old[i].v]; if (dsu.unite(u, v)) { adj[u].push_back({v, reduced_old[i].w, -1}); adj[v].push_back({u, reduced_old[i].w, -1}); } else unused.push_back(reduced_old[i]); } for (int i = 0; i < K; i++) edge_fees[i] = 1000001; // Max fee ban đầu for (size_t i = 0; i < unused.size(); ++i) { update_path(super_node[unused[i].u], super_node[unused[i].v], -1, unused[i].w); } get_subtree_people(super_node[1], -1); max_rev = max(max_rev, calculate_revenue(super_node[1], -1)); } cout << max_rev << endl; return 0; }