#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define rep(i,a,b) for(auto i = (a); i != (b); ++i)
#define REP(i,n) rep(i,0,n)
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

const ll LLINF = 1e18;
const int maxn = 1e5 + 1;

struct Edge { ll t, r, c, f; };

struct Dinic {
	vi H; vector<vector<Edge>> G;
	Dinic(int n) : H(n), G(n) {}

	void addEdge(int u, int v, ll c) {
		G[u].pb({v, (ll)G[v].size(), c, 0});
		G[v].pb({u, (ll)G[u].size()-1,0,0});
	}

	void bfs(int s) {
		fill(all(H), 0); H[s] = 1;
		queue<int> q; q.push(s);
		while (!q.empty()) {
			int v = q.front(); q.pop();
			for (Edge e : G[v]) if (!H[e.t] && e.f < e.c)
					H[e.t] = H[v]+1, q.push(e.t);
		}
	}

	ll dfs(int t, int v, ll mf) {
		if (v == t) return mf;
		ll f = 0; bool sat = true;
		for (Edge &e : G[v]) {
			if (H[e.t] != H[v] + 1 || e.f >= e.c) continue;
			ll df = dfs(t, e.t, min(mf - f, e.c - e.f));
			f += df, e.f += df, G[e.t][e.r].f -= df;
			sat &= e.f == e.c; if (mf == f) break;
		}
		if (sat) H[v] = 0;
		return f;
	}

	ll augment(int s, int t) {
		bfs(s);
		return H[t] ? dfs(t, s, LLINF) : 0;
	}

	ll maxflow(int s, int t, ll f = 0) {
		for (ll df; (df = augment(s, t));) f += df;
		return f;
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, ns;
	cin >> n >> m >> ns;

	vvii E(n + 1); // 1-based
	vector<ll> cap(n), scap(ns);

	REP(i, n) cin >> cap[i];

	REP(i, m) {
		int a, b, c;
		cin >> a >> b >> c;
		E[a].eb(b, c);
		E[b].eb(a, c);
	}

	vector< vector<ll> > D(ns, vector<ll>(n + 1, LLINF));

	REP(i, ns) {
		int loc;
		cin >> loc >> scap[i];

		// Dijkstra
		priority_queue< pair<ll, int> > pq;
		pq.emplace(-(D[i][loc] = 0LL), loc);

		while (!pq.empty()) {
			auto cur = pq.top();
			pq.pop();
			if (-cur.x > D[i][cur.y]) continue;
			for (ii nxt : E[cur.y]) {
				ll alt = ((ll) nxt.y) - cur.x;
				if (alt < D[i][nxt.x])
					pq.emplace(-(D[i][nxt.x] = alt), nxt.x);
			}
		}
	}

	// use the constructed graph to run a max-flow on.
	ll needed1 = accumulate(scap.begin(), scap.end(), 0LL);

	// variant: use minimum of sources and sinks
	ll needed2 = accumulate(cap.begin(), cap.end(), 0LL);

	// assert(needed1 >= needed2);
	ll needed = min(needed1, needed2);

	// binary search on time
	ll lo = 0, hi = LLINF;
	while (hi - lo > 1) {
		ll mi = (lo + hi) / 2;

		// construct the flowgraph
		Dinic fgraph(ns + (1 << ns) + 2);
		int vsrc = ns + (1 << ns), vsink = vsrc + 1;

		REP(i, ns) fgraph.addEdge(vsrc, i, scap[i]);

		REP(i, ns) REP(j, 1 << ns) if ((j >> i) & 1) fgraph.addEdge(i, ns + j, LLINF);

		vector<ll> sums(1 << ns, 0LL);
		REP(i, n) {
			int k = 0;
			REP(j, ns) if (D[j][i+1] < mi) k |= 1<<j;
			sums[k] += cap[i];
		}
		REP(i, 1<<ns) fgraph.addEdge(ns + i, vsink, sums[i]);

		ll fl = fgraph.maxflow(vsrc, vsink);
		// cerr << mi << ": " << fl << endl;
		if (fl >= needed) hi = mi;
		else lo = mi;
	}
	cout << lo << endl;
	return 0;
}