#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
const int MAXM = 300005;
const int MAXK = 25;
struct Edge {
int u, v, w;
};
bool compareEdges(const Edge& a, const Edge& b) {
return a.w < b.w;
}
int N, M, K;
Edge old_edges[MAXM];
pair<int, int> new_roads[MAXK];
int p_count[MAXN];
struct DSU {
int parent[MAXN];
void init(int n) { for (int i = 0; i <= n; i++) parent[i] = i; }
int find(int i) {
if (parent[i] == i) return i;
return parent[i] = find(parent[i]);
}
bool unite(int i, int j) {
int root_i = find(i), root_j = find(j);
if (root_i != root_j) { parent[root_i] = root_j; return true; }
return false;
}
} dsu, dsu_super;
int super_node[MAXN], mapping[MAXN], v_cnt;
ll super_people[MAXK * 2];
vector<Edge> reduced_old;
struct GraphEdge { int to, weight, id; };
vector<GraphEdge> adj[MAXK * 2];
ll subtree_people[MAXK * 2];
int edge_fees[MAXK];
// Tính tổng dân số trong cây con của đồ thị nén
void get_subtree_people(int u, int p) {
subtree_people[u] = super_people[u];
for (size_t i = 0; i < adj[u].size(); ++i) {
if (adj[u][i].to == p) continue;
get_subtree_people(adj[u][i].to, u);
subtree_people[u] += subtree_people[adj[u][i].to];
}
}
// Tìm đường đi và cập nhật phí cầu đường tối đa cho cạnh của Mr Greedy
bool update_path(int u, int target, int p, int w_limit) {
if (u == target) return true;
for (size_t i = 0; i < adj[u].size(); ++i) {
if (adj[u][i].to == p) continue;
if (update_path(adj[u][i].to, target, u, w_limit)) {
if (adj[u][i].id >= 0) edge_fees[adj[u][i].id] = min(edge_fees[adj[u][i].id], w_limit);
return true;
}
}
return false;
}
// Tính tổng doanh thu cho mask hiện tại
ll calculate_revenue(int u, int p) {
ll res = 0;
for (size_t i = 0; i < adj[u].size(); ++i) {
if (adj[u][i].to == p) continue;
if (adj[u][i].id >= 0) res += (ll)subtree_people[adj[u][i].to] * edge_fees[adj[u][i].id];
res += calculate_revenue(adj[u][i].to, u);
}
return res;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
if (!(cin >> N >> M >> K)) return 0;
for (int i = 0; i < M; i++) cin >> old_edges[i].u >> old_edges[i].v >> old_edges[i].w;
sort(old_edges, old_edges + M, compareEdges);
for (int i = 0; i < K; i++) cin >> new_roads[i].first >> new_roads[i].second;
for (int i = 1; i <= N; i++) cin >> p_count[i];
// Tìm MST cơ bản
dsu.init(N);
vector<Edge> mst_all;
for (int i = 0; i < M; i++) if (dsu.unite(old_edges[i].u, old_edges[i].v)) mst_all.push_back(old_edges[i]);
// Xác định các siêu đỉnh (nén đồ thị)
dsu.init(N);
for (int i = 0; i < K; i++) dsu.unite(new_roads[i].first, new_roads[i].second);
dsu_super.init(N);
for (size_t i = 0; i < mst_all.size(); ++i) {
if (dsu.unite(mst_all[i].u, mst_all[i].v)) dsu_super.unite(mst_all[i].u, mst_all[i].v);
else reduced_old.push_back(mst_all[i]);
}
memset(mapping, -1, sizeof(mapping));
v_cnt = 0;
for (int i = 1; i <= N; i++) {
int r = dsu_super.find(i);
if (mapping[r] == -1) mapping[r] = v_cnt++;
super_node[i] = mapping[r];
super_people[super_node[i]] += p_count[i];
}
ll max_rev = 0;
// Duyệt tất cả các tập con cạnh mới (2^K)
for (int mask = 1; mask < (1 << K); mask++) {
dsu.init(v_cnt);
bool cycle = false;
for (int i = 0; i < v_cnt; i++) adj[i].clear();
for (int i = 0; i < K; i++) if ((mask >> i) & 1) {
int u = super_node[new_roads[i].first], v = super_node[new_roads[i].second];
if (!dsu.unite(u, v)) { cycle = true; break; }
adj[u].push_back({v, 0, i}); adj[v].push_back({u, 0, i});
}
if (cycle) continue;
vector<Edge> unused;
for (size_t i = 0; i < reduced_old.size(); ++i) {
int u = super_node[reduced_old[i].u], v = super_node[reduced_old[i].v];
if (dsu.unite(u, v)) {
adj[u].push_back({v, reduced_old[i].w, -1});
adj[v].push_back({u, reduced_old[i].w, -1});
} else unused.push_back(reduced_old[i]);
}
for (int i = 0; i < K; i++) edge_fees[i] = 1000001; // Max fee ban đầu
for (size_t i = 0; i < unused.size(); ++i) {
update_path(super_node[unused[i].u], super_node[unused[i].v], -1, unused[i].w);
}
get_subtree_people(super_node[1], -1);
max_rev = max(max_rev, calculate_revenue(super_node[1], -1));
}
cout << max_rev << endl;
return 0;
}
