先求一下原图的最小生成树，把不在最小生成树里的边全部删掉。
Mr.Greedy 的边会替换掉若干最小生成树上的边。
一个暴力做法是，先 (2 ^ k) 枚举哪些边一定在最小生成树中，把他们加入最小生成树。然后从小到达枚举原图上的边。如果能加入就直接加入，否则就会出现一个环，那么这个环上所有 Mr.Greedy 的边权值都不能大于这条边。这样的复杂度是 (O(2^kn))
考虑优化这个暴力。显然，有一些边是无论如何都会在最小生成树里的。将 Mr.Greedy 的 (k) 条边全部插入最小生成树中，然后加入原图的边。能在此时被加入的边，一定会存在于任何一棵最小生成树中。
那么就把这些边直接缩起来。我们得到的新图中就只有不超过 (k+1) 个点，(inom{k+1}{2}) 条边。
在新图上跑原来的暴力。现在我们只需考虑 (O(k^2)) 条原图的边对 (O(k)) 条 Mr.Greedy 的边的限制。
如果直接将一条路径的值取 Min，单次复杂度是 (O(k^3))。但是事实上，因为最小生成树从小到大加边，一条边最先被赋值的时候就应该被赋到了最小值，所以可以对每个点再维护第一个没有被赋值的祖先边。总复杂度就可以做到 (O(mlogm + 2^kk^2))
代码写的有点丑。
#pragma GCC optimize("2,Ofast,inline")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int, int>
using namespace std;
const int N = 3e5 + 100;
const int inf = 0x3f3f3f3f;
template <typename T> T read(T &x) {
int f = 0;
register char c = getchar();
while (c > '9' || c < '0') f |= (c == '-'), c = getchar();
for (x = 0; c >= '0' && c <= '9'; c = getchar())
x = (x << 3) + (x << 1) + (c ^ 48);
if (f) x = -x;
return x;
}
int n, m, k, tot;
int fa[N], peo[N], tag[N], dep[N], mn[N];
LL val[N], sum[N], siz[N];
struct Edge{
int a, b, c;
bool operator < (const Edge &e) const {
return c < e.c;
}
} e[N], gdy[N];
vector<int> V, G[N];
struct UFS {
int top, u[N], v[N];
int fa[N];
LL siz[N];
void init() {
top = 0;
for (int i = 1; i <= n; ++i) {
fa[i] = i;
siz[i] = peo[i];
}
}
int find(int x) {
return (fa[x] == x) ? x : find(fa[x]);
}
void merge(int x, int y) {
x = find(x); y = find(y);
if (siz[x] < siz[y]) swap(x, y);
fa[y] = x; siz[x] += siz[y];
++top; u[top] = x; v[top] = y;
}
void cancle() {
int x = u[top], y = v[top--];
fa[y] = y; siz[x] -= siz[y];
}
} ufs, nmdp;
void dfs(int x, int f) {
dep[x] = dep[f] + 1;
sum[x] = val[x];
mn[x] = inf;
fa[x] = f;
for (int i = 0; i < G[x].size(); ++i) {
if (G[x][i] == f) continue;
dfs(G[x][i], x);
sum[x] += sum[G[x][i]];
}
}
LL solve(int S) {
for (int i = 0; i < V.size(); ++i) {
G[V[i]].clear();
}
nmdp.top = 0;
for (int i = 0; i < V.size(); ++i) {
nmdp.fa[V[i]] = V[i];
}
int now = ufs.top, flag = 1, rt = ufs.find(1);
for (int i = 0; i < k; ++i) {
if (S >> i & 1) {
int x = gdy[i + 1].a, y = gdy[i + 1].b;
if (ufs.find(x) == ufs.find(y)) flag = 0;
else {
ufs.merge(x, y);
G[x].pb(y);
G[y].pb(x);
}
}
}
if (!flag) {
while (ufs.top > now) {
ufs.cancle();
}
return 0;
}
for (int i = 1; i <= tot; ++i) {
int x = e[i].a;
int y = e[i].b;
if (ufs.find(x) == ufs.find(y)) {
tag[i] = 1;
continue;
}
ufs.merge(x, y);
G[x].pb(y);
G[y].pb(x);
}
dfs(rt, 0);
for (int i = 1; i <= tot; ++i) {
if (!tag[i]) continue;
tag[i] = 0;
int u = nmdp.find(e[i].a), v = nmdp.find(e[i].b), s = u;
while (u != v) {
if (dep[u] < dep[v]) swap(u, v);
nmdp.merge(u, s);
mn[u] = min(mn[u], e[i].c);
u = fa[u];
}
}
LL ans = 0;
for (int i = 0; i < k; ++i) {
if (S >> i & 1) {
int u = gdy[i + 1].a, v = gdy[i + 1].b;
if (dep[u] < dep[v]) swap(u, v);
ans += 1LL * mn[u] * sum[u];
}
}
while (ufs.top > now) {
ufs.cancle();
}
return ans;
}
int main() {
read(n); read(m); read(k);
for (int i = 1; i <= m; ++i) {
read(e[i].a); read(e[i].b); read(e[i].c);
}
for (int i = 1; i <= k; ++i) {
read(gdy[i].a); read(gdy[i].b);
}
for (int i = 1; i <= n; ++i) read(peo[i]);
sort(e + 1, e + m + 1);
ufs.init();
int cnt = 0;
for (int i = 1; i <= m; ++i) {
int x = ufs.find(e[i].a);
int y = ufs.find(e[i].b);
if (x == y) e[i].c = inf, ++cnt;
else ufs.merge(x, y);
}
ufs.init();
sort(e + 1, e + m + 1); m -= cnt;
for (int i = 1; i <= k; ++i) {
ufs.merge(gdy[i].a, gdy[i].b);
}
for (int i = 1; i <= m; ++i) {
int x = ufs.find(e[i].a);
int y = ufs.find(e[i].b);
if (x == y) ++tot;
else {
ufs.merge(x, y);
e[i].c = inf;
}
}
ufs.init();
for (int i = 1; i <= m; ++i) {
if (e[i].c == inf) {
ufs.merge(e[i].a, e[i].b);
}
}
for (int i = 1; i <= n; ++i) {
if (ufs.find(i) == i) {
V.pb(i);
val[i] = ufs.siz[i];
}
}
for (int i = 1; i <= k; ++i) {
gdy[i].a = ufs.find(gdy[i].a);
gdy[i].b = ufs.find(gdy[i].b);
}
sort(e + 1, e + m + 1);
for (int i = 1; i <= tot; ++i) {
e[i].a = ufs.find(e[i].a);
e[i].b = ufs.find(e[i].b);
}
LL ans = 0;
for (int i = 1; i < (1 << k); ++i) {
ans = max(ans, solve(i));
}
cout << ans << endl;
return 0;
}