#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;
}
int main(){
	int n,m,s;
	cin >> n >> m >> s; // s <= 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(s);
	for(auto &s : as)
		cin >> s.v >> s.weight, --s.v;
	vector<vector<ll>> dists(s);
	for(int i = 0; i < s; ++i)
		dists[i] = dijkstra(g, as[i].v);
	
	ll l = 0, h = 1e18;

	while(l < h){
		ll m = (l+h)/2; // Max distance m
		vector<int> masks(n);
		for(int i = 0; i < n; ++i)
			for(int j = 0; j < s; ++j)
				if(dists[j][i] <= m)
					masks[i] |= 1<<j;
		for(int m = 0; m < 1<<s; ++m){
			ll total_cover = 0;
			for(int i = 0; i < n; ++i)
				if((m | masks[i]) == m) total_cover += cs[i];
			ll cap = 0;
			for(int i = 0; i < s; ++i)
				if(m & (1<<i)) cap += as[i].weight;
			if(cap < total_cover) goto bad;
		}


		h = m;
		continue;
bad:
		l = m + 1;
	}
	cout << l << endl;
}