#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using ll = long long;
// Dijkstra
struct Edge{ int v; ll weight; };	// input edges
struct PQ{ ll d; int v; };			// distance and target
bool operator>(const PQ &l, const PQ &r){ return l.d > r.d; }
vector<ll> dijkstra(const vector<vector<Edge>> &edges, int s) {
	vector<ll> dist(edges.size(),1e18);
	priority_queue<PQ,vector<PQ>,greater<PQ>> pq;
	dist[s] = 0; pq.push({0, s});
	while (!pq.empty()) {
		auto d = pq.top().d; auto u = pq.top().v; pq.pop();
		if (d == dist[u])
			for(auto &e : edges[u]) if (dist[e.v] > d + e.weight){
				pq.push({dist[e.v] = d + e.weight, e.v});
			}
	}
	return dist;
}
// Dinic
using F = ll;
struct S{
	const int v;			// neighbour
	const int r;	// index of the reverse edge
	F f;			// current flow
	const F cap;	// capacity
	S(int v, int ri, F c) :
		v(v), r(ri), f(0), cap(c) {}
};
struct FlowGraph : vector<vector<S>> {
	FlowGraph(size_t n) : vector<vector<S>>(n) {}
	void add_edge(int u, int v, F c){ auto &t = *this;
		t[u].emplace_back(v, t[v].size(), c);
		t[v].emplace_back(u, t[u].size()-1, 0);
	}
};
struct Dinic{
	FlowGraph &edges; int V,s,t;
	vector<int> 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, 1e18)) > 0) flow += f;
		}	}
};
int main(){
	int n,m,a;
	cin >> n >> m >> a; // a <= 5
	vector<vector<Edge>> g(n);
	vector<long long> cs(n);
	long long people = 0;
	for(auto &c : cs) cin >> c, people+=c;
	while(m--){
		int u,v,w;
		cin >> u >> v >> w;
		--u, --v;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	vector<Edge> as(a);
	for(auto &s : as)
		cin >> s.v >> s.weight, --s.v;
	vector<vector<ll>> dists(a);
	for(int i = 0; i < a; ++i)
		dists[i] = dijkstra(g, as[i].v);
	
	ll l = 0, h = 1e18; // The answer is somewhere in [l,h].

	while(l < h){
		ll m = (l+h)/2; // Max distance m

		// BUILD THE FLOWGRAPH.
		FlowGraph f(a + n + 2);
		int s = a+n;
		int t = s+1;
		// s -> [0..n) -> [n..n+a) -> t
		for(int i = 0; i < n; ++i)
			f.add_edge(s, i, cs[i]);
		// 2: infinite capacity, edges i -> n+j if dist[i][j] <= m
		for(int j = 0; j < a; ++j)
			for(int i = 0; i < n; ++i)
				if(dists[j][i] <= m)
					f.add_edge(i, n + j, 1e18);

		// 3: as[i] capacity, all edges
		for(int j = 0; j < a; ++j)
			f.add_edge(n+j, t, as[j].weight);

		auto flow = Dinic(f, s, t).run();
		if(flow == people)
			h = m;
		else
			l = m + 1;
	}
	cout << l << endl;
}