#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

/*
	Binary search + naive flow
*/

using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using ii = pair<ll, ll>;
using vi = vector<ll>;
using vvi = vector<vi>;
using vii = vector<ii>;
using vvii = vector<vii>;

template<class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<class TIn, class TOut = null_type>
using order_tree = tree<TIn, TOut, less<TIn>, rb_tree_tag,
	tree_order_statistics_node_update>;

constexpr int INF = 2000000010;
constexpr ll LLINF = 9000000000000000010LL;

// FLOW
using F = ll; using W = ll; // types for flow and weight/cost
struct S{
	const int v;			// neighbour
	const int r;	// index of the reverse edge
	F f;			// current flow
	const F cap;	// capacity
	const W cost;	// unit cost
	S(int v, int ri, F c, W cost = 0) :
		v(v), r(ri), f(0), cap(c), cost(cost) {}
};
struct FlowGraph : vector<vector<S>> {
	FlowGraph(size_t n) : vector<vector<S>>(n) {}
	void add_edge(int u, int v, F c, W cost = 0){ auto &t = *this;
		t[u].emplace_back(v, t[v].size(), c, cost);
		t[v].emplace_back(u, t[u].size()-1, 0, -cost);
	}
};
struct Dinic{
	FlowGraph &edges; int V,s,t;
	vi l; vector<vector<S>::iterator> its; // levels and iterators
	Dinic(FlowGraph &edges, int s, int t) :
		edges(edges), V(edges.size()), s(s), t(t), l(V,-1), its(V) {}
	ll augment(int u, F c) { // we reuse the same iterators
		if (u == t) return c;
		for(auto &i = its[u]; i != edges[u].end(); i++){
			auto &e = *i;
			if (e.cap > e.f && l[u] < l[e.v]) {
				auto d = augment(e.v, min(c, e.cap - e.f));
				if (d > 0) { e.f += d; edges[e.v][e.r].f -= d; return d; }
			}	}
		return 0;
	}
	ll run() {
		ll flow = 0, f;
		while(true) {
			fill(l.begin(), l.end(),-1); l[s]=0; // recalculate the layers
			queue<int> q; q.push(s);
			while(!q.empty()){
				auto u = q.front(); q.pop();
				for(auto &&e : edges[u]) if(e.cap > e.f && l[e.v]<0)
					l[e.v] = l[u]+1, q.push(e.v);
			}
			if (l[t] < 0) return flow;
			for (int u = 0; u < V; ++u) its[u] = edges[u].begin();
			while ((f = augment(s, INF)) > 0) flow += f;
		}	}
};
//-FLOW

vi dijkstra(int s, const vvii &E) {
	vi dst(E.size(), LLINF);
	min_heap<ii> mh;
	mh.push({dst[s] = 0, s});
	while (!mh.empty()) {
		int u, v; ll d, w;
		tie(d, u) = mh.top();
		mh.pop();
		if (dst[u] < d) continue;
		for (ii vw : E[u]) {
			tie(v, w) = vw;
			if (dst[v] > d + w)
				mh.push({dst[v] = d + w, v});
		}
	}
	return dst;
}

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

	// IO
	int n, m, s;
	cin >> n >> m >> s;

	vi pop(n);
	for (ll &p : pop) cin >> p;
	ll total_pop = accumulate(pop.begin(), pop.end(), 0LL);

	vvii E(n);
	while (m--) {
		int u, v;
		ll w;
		cin >> u >> v >> w;
		E[u-1].push_back({v-1, w});
		E[v-1].push_back({u-1, w});
	}

	vi shelcap(s);
	vvi dtos(s);
	for (int i = 0; i < s; ++i) {
		int si;
		cin >> si >> shelcap[i];
		si -= 1;

		// Get the distance between this shelter and each location.
		dtos[i] = dijkstra(si, E);
	}
	//-IO

	ll l = 0LL, r = 1e15;
	while (l < r) {
		// Test if time t works.
		ll t = (l + r) / 2;

		// Build the flowgraph.
		FlowGraph fg(s + n + 2);
		int SOURCE = s + n, SINK = s + n + 1;
		for (int i = 0; i < n; ++i) {
			if (pop[i] > 0) {
				fg.add_edge(SOURCE, i, pop[i]);
				for (int j = 0; j < s; ++j)
					if (dtos[j][i] <= t)
						fg.add_edge(i, n + j, LLINF);
			}
		}
		for (int i = 0; i < s; ++i)
			fg.add_edge(n + i, SINK, shelcap[i]);

		// And test.
		ll flow = Dinic(fg, SOURCE, SINK).run();
		if (flow < total_pop)
			l = t + 1;
		else
			r = t;
	}

	cout << l << endl;
	
	return 0;
}