#include <bits/stdc++.h> using namespace std; #define int long long struct DSU{ vector<int> parent,sz; DSU(int n){ sz.resize(n,1); parent.resize(n); for (int i = 0; i<n; i++){ parent[i] = i; } } int find(int x){ if (x == parent[x]){ return x; } return parent[x] = find(parent[x]); } bool merge(int a, int b){ a = find(a); b = find(b); if (a == b) return false; if (sz[a] < sz[b]) swap(a,b); parent[b] = a; sz[a] += sz[b]; return true; } bool sam(int a, int b){ //check if two nodes are in the same component int x = find(a); int xx = find(b); return (x == xx); } }; const int MAXN = 1e5+5; vector<pair<int,int>> adj[MAXN]; int sz[MAXN]; int tot = 0; int arr[MAXN]; int par[MAXN]; int depth[MAXN]; void dfs_sz(int x, int p){ sz[x] = arr[x]; par[x] = p; for (auto v : adj[x]){ auto [u,w] = v; if (u == p) continue; dfs_sz(u,x); sz[x] += sz[u]; depth[u] = depth[x]+1; } } signed main(){ int n,m,k; cin >> n >> m >> k; vector<array<int,3>> edge(m); for (int i = 0; i<m; i++){ int a,b,w; cin >> a >> b >> w; a--;b--; edge[i] = {w,a,b}; } sort(edge.begin(), edge.end()); vector<pair<int,int>> mm; for (int i = 0; i<k; i++){ int a,b; cin >> a >> b; a--;b--; mm.push_back({a,b}); } for (int i = 0; i<n; i++){ cin >> arr[i]; } vector<int> ans(k, 0); for (int z = 0; z<k; z++){ auto [a,b] = mm[z]; //we need to find the cut between a,b DSU dsu(n); for (int i = 0; i<edge.size(); i++){ int aa = edge[i][1]; int bb = edge[i][2]; int ww = edge[i][0]; dsu.merge(aa, bb); if (dsu.sam(a, b)){ ans[z] = ww; break; } } edge.push_back({ans[z],a,b}); //cout << ans[z] << " " << a << " " << b << '\n'; sort(edge.begin(), edge.end()); } //now we just construct the MST and then dfs //simply construct subtree sizes DSU dsu(n); for (int i = 0; i<edge.size(); i++){ auto [w,a,b] = edge[i]; if (dsu.merge(a,b)){ adj[b].push_back({a,w}); adj[a].push_back({b,w}); } } dfs_sz(0,-1); for (int i = 0; i<n; i++){ //cout << sz[i] << " "; } depth[0] = 0; for (int i = 0; i<k; i++){ auto [a,b] = mm[i]; if (depth[a] > depth[b]) swap(a,b); //we ensure A is always parent tot += ans[i] * sz[b]; } cout << tot << '\n'; return 0; }