#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 FordFulkerson {
	int V;
	vi par;
	vector<vector<edge>> g;

	FordFulkerson(int n) : V(n), par(n, -1), g(n) {}

	inline 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});
	}

	ll dfs(int s, int t, int v, ll mf) {
		if (v == t) {
			while (v != s) {
				edge &bk = g[v][par[v]];
				edge &fw = g[bk.t][bk.r];
				bk.f -= mf;
				fw.f += mf;
				assert(fw.f <= fw.c);
				v = bk.t;
			}
			return mf;
		}

		for (edge e : g[v]) {
			if (e.f >= e.c || par[e.t] >= 0) continue;
			par[e.t] = e.r; // reverse edge
			ll ret = dfs(s, t, e.t, min(mf, e.c - e.f));
			par[e.t] = -1;
			if (ret) return ret;
		}
		return 0;
	}
};
*/

struct Dinic {
	int V;
	vi h;
	vector< vector<edge> > g;

	Dinic(int n) : V(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< pair<ll, ii> > dists;
	dists.reserve(ns * N);

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

		// Dijkstra
		vector<ll> dist(N + 1, LLINF);

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

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

		REP(j, N) dists.eb(dist[j+1], ii(i, j));
	}

	// 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);

	// sort by increasing time
	sort(all(dists));

	/*for (auto it : dists) {
		cerr << it.y.x << " -> " << it.y.y << ": " << it.x << endl;
	}*/

	// binary search on time
	int lo = 0, hi = (int) dists.size();
	while (hi - lo > 1) {
		int mi = (lo + hi) / 2;

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

		REP(i, ns) fgraph.addEdge(vsrc, i, scap[i]);
		REP(i, mi) fgraph.addEdge(dists[i].y.x, ns + dists[i].y.y, LLINF);
		REP(i, N) fgraph.addEdge(ns + i, vsink, cap[i]);

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