#include<bits/stdc++.h> using namespace std; #define maxn 100'007 #define BIT 24 struct edge { int u, v, w; bool operator < (edge &b) { return w < b.w; } bool operator () (edge &b) { return w < b.w; } }; class DSU { public: int N; int par[maxn]; void init(int n) { N = n; iota(par, par+N+1, 0); } int find(int u) { return par[u] == u ? u : par[u] = find(par[u]); } bool unite(int u, int v) { u = find(u); v = find(v); if(u == v) return 0; par[v] = u; return 1; } } fmt, nt; int n, m, k; edge arr[3*maxn], ebi[BIT]; bool MST[3*maxn]; long long pop[maxn]; long long ans = 0; bool mask[24]; int g[BIT][BIT], sz[BIT]; int h[BIT], par[BIT]; int mx[BIT]; long long sum[BIT]; void fOrder(int &a, vector<int> &arr) { a = int(lower_bound(arr.begin(), arr.end(), a) - arr.begin()) + 1; } inline void dfs(int u) { for(int i=0;i<sz[u];++i) if(g[u][i] != par[u]) { par[g[u][i]] = u; h[g[u][i]] = h[u] + 1; dfs(g[u][i]); } } inline void dfs2(int u) { sum[u] = pop[u]; for(int i=0;i<sz[u];++i) if(g[u][i] != par[u]) { dfs2(g[u][i]); sum[u] += sum[g[u][i]]; } } void solve() { cin >> n >> m >> k; for(int i=1;i<=m;++i) { cin >> arr[i].u >> arr[i].v >> arr[i].w; } fmt.init(n); nt.init(n); sort(arr+1,arr+1+m); for(int i=1;i<=m;++i) { if(fmt.unite(arr[i].u, arr[i].v)) { MST[i] = 1; } } fmt.init(n); vector<edge> se; for(int i=1;i<=k;++i) { cin >> ebi[i].u >> ebi[i].v; fmt.unite(ebi[i].u, ebi[i].v); } for(int i=1;i<=n;++i) { cin >> pop[i]; } for(int i=1;i<=m;++i) if(MST[i]) { if(fmt.unite(arr[i].u, arr[i].v)) { nt.unite(arr[i].u, arr[i].v); } else { se.push_back(arr[i]); } } vector<int> bag;int sr = nt.find(1); for(int i=1;i<=k;++i) { ebi[i].u = nt.find(ebi[i].u); ebi[i].v = nt.find(ebi[i].v); bag.push_back(ebi[i].u); bag.push_back(ebi[i].v); } for(auto& e:se) { e.u = nt.find(e.u); e.v = nt.find(e.v); bag.push_back(e.u); bag.push_back(e.v); } for(int i=1;i<=n;++i) if(nt.find(i) != i) { pop[nt.find(i)] += pop[i]; } sort(bag.begin(), bag.end()); bag.erase(unique(bag.begin(), bag.end()), bag.end()); fOrder(sr, bag); for(int i=1;i<=k;++i) { fOrder(ebi[i].u, bag); fOrder(ebi[i].v, bag); //cerr << ebi[i].u << ' ' << ebi[i].v << '\n'; } for(auto& e:se) { fOrder(e.u, bag); fOrder(e.v, bag); //cerr << e.u << ' ' << e.v << '\n'; } for(int i=0;i<bag.size();++i) { pop[i+1] = pop[bag[i]]; //cerr << pop[i+1] << " \n"[i==bag.size()-1]; } n = bag.size(); for(int state = 1; state < (1<<k); ++state) { for(int i=1;i<=n;++i) { sz[i] = 0; mx[i] = INT_MAX; nt.par[i] = fmt.par[i] = i; } bool no = 0; for(int i=0;i<k;++i) if(state>>i&1) { if(fmt.unite(ebi[i+1].u, ebi[i+1].v)) { g[ebi[i+1].u][sz[ebi[i+1].u]++] = ebi[i+1].v; g[ebi[i+1].v][sz[ebi[i+1].v]++] = ebi[i+1].u; } else { no = 1; break; } } if(no) continue; for(int i=0;i<se.size();++i) { if(fmt.unite(se[i].u, se[i].v)) { g[se[i].u][sz[se[i].u]++] = se[i].v; g[se[i].v][sz[se[i].v]++] = se[i].u; } else mask[i] = 1; } h[sr] = par[sr] = 0; dfs(sr); for(int i=0;i<se.size();++i) { if(mask[i]) { int u = se[i].u, v = se[i].v; while(u != v) { if(h[u] < h[v]) swap(u,v); mx[u] = min(mx[u], se[i].w); while(par[u] > 0 and mx[par[u]] != INT_MAX) { nt.unite(par[u], u); u = nt.find(u); } u = par[u]; } mask[i] = 0; } } dfs2(sr); long long total = 0; for(int i=0;i<k;++i) if(state>>i&1) { int u = ebi[i+1].u, v = ebi[i+1].v; if(h[u] > h[v]) total += mx[u] * sum[u]; else total += mx[v] * sum[v]; } ans = max(ans, total); } cout << ans; } int main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); solve(); return 0; } /* 5 5 1 3 5 2 1 2 3 2 3 5 2 4 4 4 3 6 1 3 10 20 30 40 50 */