#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using ll = long long;
using vi = vector<int>;
// 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
	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) {}
	F* 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);
		return &t[u].back().cap;
	}
	void reset(){
		for(auto &v : *this)
			for(auto &e : v)
				e.f = 0;
	}
};




class Push_Relabel {
public:
	FlowGraph &g; // directed
	int V, s, t; // Vertices, source and sink
	vi h, hc, qc; // height, height count, queuecount
	vector<ll> x; // excess

	Push_Relabel(FlowGraph &g, int s, int t) :
		g(g), V(g.size()), s(s), t(t), h(V,0), hc(2*V,0), qc(V,0), x(V,0){
		hc[0] = V;
	}

	long long run(){
		// we initialize all heights using a BFS starting at `t`
		queue<int> q; q.push(t);
		while(!q.empty()){
			int u = q.front(); q.pop();
			for(auto && x : g[u])
				if(h[x.v] == 0 && x.v != t)
					hc[0]--,h[x.v] = h[u]+1,hc[h[x.v]]++, q.push(x.v);
		}

		// now set height of `s`
		hc[h[s]]--; h[s]=V; hc[V]++;

		// and push initial flows
		for(auto &&e : g[s]){
			int flow = e.cap;
			e.f = flow;
			g[e.v][e.r].f -=flow;
			x[e.v] += flow; // += for multiple edges to it
			x[s]  -= flow;
		}
		// keep a queue of overflowing vertices
		// (FIFO heuristic -> V^3)
		q = queue<int>();
		for(auto &&e : g[s])
			if(e.v!=t && qc[e.v] == 0)
				q.push(e.v), qc[e.v]=1;
		while(!q.empty()){
			int u = q.front(), m = 2e9;
			for(auto &&e : g[u]) if( e.cap > e.f){
				if(h[u] > h[e.v]){
					// push flow from `u` to `v`
					int flow = min(x[u], e.cap - e.f);
					e.f += flow;
					g[e.v][e.r].f -= flow;
					x[u] -= flow;
					x[e.v] += flow;

					// push overflowing `v` on queue
					if(qc[e.v] == 0 && e.v != s && e.v != t)
						qc[e.v]=1, q.push(e.v);

					if(x[u] == 0) break; // stop when done
				} else
					m = min(m, h[e.v]);
			}
			if(x[u]!=0){
				if(m!=2e9){
					hc[h[u]]--;
					// apply gap heuristic
					if(hc[h[u]] == 0) // raise h[u] to V to V+1
						for(auto &&ht : h) if(ht > h[u] && ht < V)
							hc[ht]--, ht=V+1, hc[ht]++;
					h[u] = m+1;
					hc[h[u]]++;
				}
			} else qc[u]=0, q.pop();
		}
		return x[t]; // this is just the total flow
	}
};

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

	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);
	ll max_dist = 0;
	for(int i = 0; i < a; ++i){
		dists[i] = dijkstra(g, as[i].v);
		max_dist = max(max_dist, *max_element(dists[i].begin(), dists[i].end()));
	}
	
	ll l = 0, h = max_dist+1; // The answer is somewhere in [l,h].

	// BUILD THE FLOWGRAPH.
	FlowGraph f(a + n + 2);
	int s = a+n;
	int t = s+1;
	// s -> [0..n) -> [n..n+a) -> t
	// degrees: n, 1+a, 1+n, a
	// 1: cl[mask] capacity, all edges
	f[s].reserve(n);
	f[t].reserve(a);
	for(int i = 0; i < n; ++i)
		f[i].reserve(1+a);
	for(int i=n; i < n+a; ++i)
		f[i].reserve(1+n);

	for(int i = 0; i < n; ++i)
		if(cs[i] > 0)
			f.add_edge(s, i, cs[i]);
	// 2: infinite capacity, edges i -> n+j if dist[i][j] <= m
	vector<vector<ll*>> cross_capacities(a, vector<ll*>(n));
	for(int j = 0; j < a; ++j)
		for(int i = 0; i < n; ++i)
			if(cs[i] > 0)
				cross_capacities[j][i] = f.add_edge(i, n + j, 0);

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

	while(l < h){
		ll m = (l+h)/2; // Max distance m
		f.reset();
		for(int j = 0; j < a; ++j)
			for(int i = 0; i < n; ++i)
				if(cs[i] > 0)
					*cross_capacities[j][i] = dists[j][i] <= m ? 1e18 : 0;
		ll flow = Push_Relabel(f, s, t).run();
		if(flow == people)
			h = m;
		else
			l = m + 1;
	}
	cout << l << endl;
}