/*input
6 5 3
5 1 1
2 6 2
5 4 3
1 2 4
2 3 5
1 5
1 6
4 6
9 6 6 1 8 6
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
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
const int MAXN = 1e5 + 6, MAXM = 3e5 + 5, MAXK = 22;
const int INF = 1e8;
struct edge_t
{
int u, v, c;
edge_t(int _u = 0, int _v = 0, int _c = 0):
u(_u), v(_v), c(_c) {}
};
struct dsu_t
{
int N;
vector<int> vec;
void init(int _N)
{
N = _N;
vec.resize(N + 1);
for (int i = 1; i <= N; ++i) vec[i] = -1;
}
int root(int x)
{
return (vec[x] < 0 ? x : vec[x] = root(vec[x]));
}
bool same(int x, int y)
{ return root(x) == root(y); }
void join(int x, int y)
{
x = root(x), y = root(y);
if (x == y) return;
if (vec[x] > vec[y]) swap(x, y);
vec[x] += vec[y];
vec[y] = x;
}
};
int N, M, K, C = 0;
int comp_id[MAXN];
int64_t P[MAXN], comp_weight[MAXK], subtree[MAXK], edge_weight[MAXK];
vector<edge_t> edges, extra, comp_edges, copy_edges;
dsu_t comp_dsu;
int comp_dist[MAXK][MAXK], edge_len[MAXK], dep[MAXK], par[MAXK];
bool weak_edge[MAXM], in_tree[MAXM];
vector<int> tree[MAXK];
template <typename T>
void minimize(T &x, T y)
{ x = (x < y ? x : y); }
template <typename T>
void maximize(T &x, T y)
{ x = (x > y ? x : y); }
void dfs_tree(int u, int p)
{
par[u] = p;
subtree[u] = comp_weight[u];
for (int v : tree[u]) {
if (v != p) {
dep[v] = dep[u] + 1;
dfs_tree(v, u);
subtree[u] += subtree[v];
}
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M >> K;
edges.resize(M);
for (auto &e : edges) cin >> e.u >> e.v >> e.c;
sort(edges.begin(), edges.end(), [&](edge_t &lhs, edge_t &rhs) { return lhs.c < rhs.c; });
extra.resize(K);
for (auto &e : extra) cin >> e.u >> e.v;
for (int i = 1; i <= N; ++i) cin >> P[i];
comp_dsu.init(N);
for (auto &e : extra) comp_dsu.join(e.u, e.v);
for (int i = 0; i < M; ++i) {
auto &e = edges[i];
if (not comp_dsu.same(e.u, e.v)) {
comp_dsu.join(e.u, e.v);
weak_edge[i] = true;
}
}
comp_dsu.init(N);
for (int i = 0; i < M; ++i) {
if (weak_edge[i]) {
comp_dsu.join(edges[i].u, edges[i].v);
}
}
for (int i = 1; i <= N; ++i) {
if (comp_dsu.root(i) == i) comp_id[i] = ++C;
}
for (int i = 1; i <= N; ++i) {
if (comp_dsu.root(i) != i) comp_id[i] = comp_id[comp_dsu.root(i)];
}
// for (int i = 1; i <= N; ++i) cout << "id " << i << ": " << comp_id[i] << endl;
for (auto &e : extra) e.u = comp_id[e.u], e.v = comp_id[e.v];
assert(C <= K + 1);
for (int i = 1; i <= N; ++i) {
comp_weight[comp_id[i]] += P[i];
}
// for (int i = 1; i <= C; ++i) cout << "weight " << i << ": " << comp_weight[i] << endl;
for (int u = 1; u <= C; ++u) {
for (int v = 1; v <= C; ++v) {
comp_dist[u][v] = INF;
}
}
for (auto &e : edges) {
minimize(comp_dist[comp_id[e.u]][comp_id[e.v]], e.c);
minimize(comp_dist[comp_id[e.v]][comp_id[e.u]], e.c);
}
for (int u = 2; u <= C; ++u) {
for (int v = 1; v < u; ++v) {
if (comp_dist[u][v] != INF) {
comp_edges.emplace_back(u, v, comp_dist[u][v]);
}
}
}
sort(comp_edges.begin(), comp_edges.end(), [&](edge_t &lhs, edge_t &rhs) { return lhs.c < rhs.c; });
comp_dsu.init(C);
for (auto &e : comp_edges) {
if (not comp_dsu.same(e.u, e.v)) {
copy_edges.push_back(e);
comp_dsu.join(e.u, e.v);
}
}
comp_edges = move(copy_edges);
assert((int) comp_edges.size() == C - 1);
assert(comp_dsu.vec[comp_dsu.root(1)] == -C);
int64_t optimal = 0;
for (int mask = 0; mask < (1 << K); ++mask) {
comp_dsu.init(C);
for (int i = 1; i <= C; ++i) tree[i].clear();
bool cycle = false;
for (int i = 0; i < K; ++i) if ((mask >> i) & 1) {
auto &e = extra[i];
if (comp_dsu.same(e.u, e.v)) {
cycle = true;
break;
}
comp_dsu.join(e.u, e.v);
tree[e.u].push_back(e.v);
tree[e.v].push_back(e.u);
}
if (cycle) continue;
for (int i = 0; i < (int) comp_edges.size(); ++i) {
auto &e = comp_edges[i];
if (not comp_dsu.same(e.u, e.v)) {
comp_dsu.join(e.u, e.v);
tree[e.u].push_back(e.v);
tree[e.v].push_back(e.u);
in_tree[i] = true;
} else in_tree[i] = false;
}
assert((int) comp_edges.size() == C - 1);
assert(comp_dsu.vec[comp_dsu.root(1)] == -C);
dep[comp_id[1]] = 0;
dfs_tree(comp_id[1], 0);
for (int i = 1; i <= C; ++i) edge_len[i] = INF;
for (int i = 0; i < (int) comp_edges.size(); ++i) if (not in_tree[i]) {
int u = comp_edges[i].u, v = comp_edges[i].v, c = comp_edges[i].c;
if (dep[u] < dep[v]) swap(u, v);
while (dep[u] > dep[v]) minimize(edge_len[u], c), u = par[u];
while (u != v) minimize(edge_len[u], c), minimize(edge_len[v], c), u = par[u], v = par[v];
}
int64_t total = 0;
// cout << "mask " << mask << endl;
for (int i = 0; i < K; ++i) if ((mask >> i) & 1) {
auto &e = extra[i];
int x = (dep[e.u] < dep[e.v] ? e.v : e.u);
// cout << i << ": " << x << " - " << subtree[x] << ' ' << edge_len[x] << endl;
total += subtree[x] * edge_len[x];
}
maximize(optimal, total);
}
cout << optimal << endl;
}
