# 2. 题解

• 如果选择的边构成了环，那么这种选择方式不合法，直接 continue
• 对于合法的选择方案，从小到大依次加入 $k ^ 2$条边
• 如果当前加入的边的两个端点还未被联通，则联通这两个端点
• 如果当前加入的边的两个端点已经被联通了，则树上这两点之间的路径上的可定价边的最大价格不得超过当前这条边的价格

#include <bits/stdc++.h>

#define NS (100005)
#define MS (300005)
#define KS (25)
#define FIR first
#define SEC second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

struct Edge {int u, v, d;} E[MS], Q[MS];

int n, m, k, Su[KS], Sv[KS], Peo[NS], Blk[NS], bc, qc;

LL Man[KS];

int fa[NS];

int findf(int a) {return fa[a] == a ? a : fa[a] = findf(fa[a]);}

bool Key_Edge[MS];

bool cmp(Edge a, Edge b) {return a.d < b.d;}

void Mini()
{
for (int i = 1; i <= n; i += 1) fa[i] = i;
int tot = 0;
for (int i = 0; i < k; i += 1)
if (findf(Su[i]) != findf(Sv[i]))
fa[findf(Su[i])] = findf(Sv[i]), tot++;
sort(E + 1, E + 1 + m, cmp);
for (int i = 1; tot < n - 1; i += 1)
if (findf(E[i].u) != findf(E[i].v))
{
fa[findf(E[i].u)] = findf(E[i].v);
Key_Edge[i] = 1, tot++;
}
for (int i = 1; i <= n; i += 1) fa[i] = i;
for (int i = 1; i <= m; i += 1)
if (Key_Edge[i]) fa[findf(E[i].u)] = findf(E[i].v);
Blk[findf(1)] = bc = 1;
for (int i = 2; i <= n; i += 1)
if (fa[i] == i && !Blk[i]) Blk[i] = ++bc;
for (int i = 1; i <= n; i += 1)
Blk[i] = Blk[findf(i)], Man[Blk[i]] += Peo[i];
for (int i = 1; i <= m; i += 1)
if (findf(E[i].u) != findf(E[i].v))
{
fa[findf(E[i].u)] = findf(E[i].v), Q[++qc] = E[i];
}
}

vector<PII> g[KS];

int pre[KS], dis[KS], dep[KS];

bool book[KS];

LL ans, res;

void Init(int a)
{
for (int i = 0, tmp; i < g[a].size(); i += 1)
if (tmp = g[a][i].FIR, tmp != pre[a])
{
pre[tmp] = a, dis[tmp] = g[a][i].SEC;
if (dis[tmp] > 1e9) book[tmp] = 1;
dep[tmp] = dep[a] + 1, Init(tmp);
}
}

void Cal(int a, int tot)
{
if (book[a]) tot += dis[a];
res += Man[a] * tot;
for (int i = 0, tmp; i < g[a].size(); i += 1)
if (tmp = g[a][i].FIR, tmp != pre[a])
Cal(tmp, tot);
}

int main(int argc, char const* argv[])
{
IN(n), IN(m), IN(k);
for (int i = 1; i <= m; i += 1) IN(E[i].u), IN(E[i].v), IN(E[i].d);
for (int i = 0; i < k; i += 1) IN(Su[i]), IN(Sv[i]);
for (int i = 1; i <= n; i += 1) IN(Peo[i]);
Mini();
for (int bs = 1; bs < (1 << k); bs += 1)
{
for (int i = 1; i <= bc; i += 1) book[i] = 0, g[i].clear(), fa[i] = i;
for (int i = 0; i < k; i += 1)
if ((bs >> i) & 1)
{
if (findf(Blk[Su[i]]) == findf(Blk[Sv[i]])) goto end;
fa[findf(Blk[Su[i]])] = findf(Blk[Sv[i]]);
g[Blk[Su[i]]].push_back(PII(Blk[Sv[i]], INT_MAX));
g[Blk[Sv[i]]].push_back(PII(Blk[Su[i]], INT_MAX));
}
for (int i = 1; i <= qc; i += 1)
if (findf(Blk[Q[i].u]) != findf(Blk[Q[i].v]))
{
fa[findf(Blk[Q[i].u])] = findf(Blk[Q[i].v]);
g[Blk[Q[i].u]].push_back(PII(Blk[Q[i].v], Q[i].d));
g[Blk[Q[i].v]].push_back(PII(Blk[Q[i].u], Q[i].d));
}
Init(1);
for (int i = 1; i <= qc; i += 1)
{
int a = Blk[Q[i].u], b = Blk[Q[i].v], c = Q[i].d;
while (a != b)
{
if (dep[a] > dep[b]) swap(a, b);
dis[b] = min(dis[b], c), b = pre[b];
}
}
res = 0, Cal(1, 0), ans = max(ans, res);
end : continue;
}
printf("%lld\n", ans);
return 0;
}