\(k\le 20\)，考慮 \(O(2^k)\) 暴力枚舉加入的邊。但是邊數很大，時間復雜度很高無法承受。

考慮在一開始強制選這 \(k\) 條邊，然后跑最小生成樹，此時加入的邊就是一定會加入的邊。設這個邊集為 \(S\)。

將 \(S\) 連接的連通塊縮成點，點數為 \(O(k)\)。再在原圖上對這些點跑最小生成樹，設加入的邊集為 \(T\)，則 \(T\) 為加入那 \(k\) 條邊后有可能在最小生成樹中的邊。數量也為 \(O(k)\)。

然后暴力枚舉強制加入的邊，用 \(T\) 跑出最小生成樹，再用 \(T\) 中的非樹邊限制強制加入的邊即可。具體地，對于一條非樹邊 \((u,v)\)，樹上 \(u\) 到 \(v\) 的路徑中的所有邊都應該大于等于這條非樹邊的邊權。暴力跳父親即可。

考慮統計答案，只需要計算通過每條邊的人數，用 dfs 計算子樹權值和即可。

時間復雜度 \(O(m\log m+2^kk^2)\)。

#include<bits/stdc++.h>
#define int long long
#define il inline
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=3e5+5;
int n,m,k,a[maxn],bel[maxn];
bool vis[maxn];
vector<int> dk;
vector<pii> e[maxn];
struct edge{
	int u,v,w;
	il bool operator<(const edge &x)const{
		return w<x.w;
	}
}em[maxn],ek[maxn];
vector<edge> et;
int fa[maxn],sz[maxn],ans;
int mxe[maxn],dep[maxn],tof[maxn];
il void init(){
	for(int i=1;i<=n;i++){
		fa[i]=i,sz[i]=1;
	}
}
il int find(int x){
	return x!=fa[x]?fa[x]=find(fa[x]):x;
}
il void merge(int u,int v){
	u=find(u),v=find(v);
	if(u==v){
		return ;
	}
	if(sz[u]>sz[v]){
		sz[u]+=sz[v],fa[v]=u;
	}
	else{
		sz[v]+=sz[u],fa[u]=v;
	}
}
il void dfs(int u){
	dep[u]=dep[fa[u]]+1;
	sz[u]=a[u];
	for(pii i:e[u]){
		int v=i.fir,w=i.sec;
		if(v!=fa[u]){
			fa[v]=u;
			tof[v]=w;
			dfs(v);
			sz[u]+=sz[v];
		}
	}
}
il void solve(int S){
	for(int u:dk){
		fa[u]=u,sz[u]=1,e[u].clear();
	}
	for(int i=1,u,v;i<=k;i++){
		if(S>>(i-1)&1){
			u=bel[ek[i].u],v=bel[ek[i].v];
			if(find(u)==find(v)){
				return ;
			}
			merge(u,v);
			e[u].pb(mp(v,-i));
			e[v].pb(mp(u,-i));
		}
	}
	for(int i=0;i<et.size();i++){
		vis[i]=0;
	}
	for(int i=0,u,v,w;i<et.size();i++){
		u=et[i].u,v=et[i].v,w=et[i].w;
		if(find(u)!=find(v)){
			merge(u,v);
			vis[i]=1;
			e[u].pb(mp(v,w));
			e[v].pb(mp(u,w));
		}
	}
	for(int i=1;i<=k;i++){
		mxe[i]=INT_MAX;
	}
	for(int u:dk){
		dep[u]=tof[u]=fa[u]=sz[u]=0;
	}
	dfs(bel[1]);
//	puts("666");
	for(int i=0,u,v,w;i<et.size();i++){
//		cout<<i<<"\n";
		if(vis[i]){
			continue;
		}
		u=et[i].u,v=et[i].v,w=et[i].w;
		if(dep[u]<dep[v]){
			swap(u,v);
		}
//		cout<<dep[u]<<" "<<dep[v]<<"\n";
		while(dep[u]>dep[v]){
//			puts("666");
			if(tof[u]<0){
				mxe[-tof[u]]=min(mxe[-tof[u]],w);
			}
			u=fa[u];
		}
		while(u!=v){
			if(tof[u]<0){
				mxe[-tof[u]]=min(mxe[-tof[u]],w);
			}
			if(tof[v]<0){
				mxe[-tof[v]]=min(mxe[-tof[v]],w);
			}
			u=fa[u],v=fa[v];
		}
	}
	for(int u:dk){
		if(tof[u]<0){
			tof[u]=-mxe[-tof[u]];
		}
	}
	int res=0;
	for(int u:dk){
		if(tof[u]<0){
			res-=tof[u]*sz[u];
		}
	}
	ans=max(ans,res);
}
namespace cplx{
	bool end;
	il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
//	cout<<cplx::usdmem();
	ios::sync_with_stdio(0),cin.tie(0);
//	freopen("toll5.in","r",stdin);
	cin>>n>>m>>k;
//	cout<<n<<" "<<m<<" "<<k<<"\n";
	for(int i=1;i<=m;i++){
		cin>>em[i].u>>em[i].v>>em[i].w;
	}
	init(),sort(em+1,em+m+1);
	for(int i=1;i<=k;i++){
		cin>>ek[i].u>>ek[i].v;
		merge(ek[i].u,ek[i].v);
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1,u,v;i<=m;i++){
		u=em[i].u,v=em[i].v;
		if(find(u)!=find(v)){
			merge(u,v);
			vis[i]=1;
		}
	}
	init();
	for(int i=1,u,v;i<=m;i++){
		if(vis[i]){
			u=find(em[i].u);
			v=find(em[i].v);
			if(sz[u]>sz[v]){
				sz[u]+=sz[v];
				a[u]+=a[v];
				fa[v]=u;
			}
			else{
				sz[v]+=sz[u];
				a[v]+=a[u];
				fa[u]=v;
			}
		}
	}
	for(int i=1;i<=n;i++){
		bel[i]=find(i);
		if(bel[i]==i){
			dk.pb(i);
		}
	}
	init();
	for(int i=1,u,v,w;i<=m;i++){
		u=bel[em[i].u],v=bel[em[i].v],w=em[i].w;
		if(find(u)!=find(v)){
			et.pb((edge){u,v,w});
			merge(u,v);
		}
	}
	for(int S=0;S<1<<k;S++){
//		cout<<bitset<15>(S)<<"\n";
		solve(S);
	}
	cout<<ans;
	return 0;
}
}
signed main(){return asbt::main();}
/*
100000 299989 12
*/