import java.io.*;
import java.util.*;

public class LudoFordFulkerson {

	public static Scanner sc;
	public static int read() {
		return sc.nextInt();
	}

	public static class FwEdge {
		int to, len;
		public FwEdge(int to, int len) {
			this.to = to;
			this.len = len;
		}
	}

	public static class Relax {
		int to;
		long relaxDist;

		public Relax(int to, long relaxDist) {
			this.to = to;
			this.relaxDist = relaxDist;
		}
	}

	public static class Shelter {
		int v, cap;
		long[] dist;

		public Shelter(int v, int cap) {
			this.v = v;
			this.cap = cap;
		}

		void runDijkstra(ArrayList<FwEdge>[] g) {
			dist = new long[g.length];
			PriorityQueue<Relax> pq = new PriorityQueue<Relax>(1,
				(a, b) -> ((Long) a.relaxDist).compareTo(b.relaxDist)
			);
			for (int i = 0; i < g.length; i++) dist[i] = Long.MAX_VALUE;
			pq.add(new Relax(this.v, dist[this.v] = 0));

			Relax cur;
			while ((cur = pq.poll()) != null) {
				if (cur.relaxDist != dist[cur.to])
					continue;
				for (FwEdge fw : g[cur.to]) {
					long alt = cur.relaxDist + fw.len;
					if (alt < dist[fw.to])
						pq.add(new Relax(fw.to, dist[fw.to] = alt));
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		sc = new Scanner(System.in);
		
		// all zero based
		int N = read(), M = read(), S = read();
		int[] P = new int[N];
		ArrayList<FwEdge>[] graph = (ArrayList<FwEdge>[]) new ArrayList[N];
		Shelter[] sh = new Shelter[S];

		for (int i = 0; i < N; i++) {
			P[i] = read();
			graph[i] = new ArrayList<FwEdge>();
		}

		while (M-- > 0) {
			int a = read() - 1, b = read() - 1, c = read();
			graph[a].add(new FwEdge(b, c));
			graph[b].add(new FwEdge(a, c));
		}

		for (int i = 0; i < S; i++) {
			sh[i] = new Shelter(read() - 1, read());

			sh[i].runDijkstra(graph);
		}

		long need1 = 0, need2 = 0;
		for (Shelter s : sh) need1 += s.cap;
		for (int i = 0; i < N; i++) need2 += P[i];
		long needed = Math.min(need1, need2);

		long lo = 0, hi = Long.MAX_VALUE;
		while (hi - lo > 1L) {
			long mi = lo + (hi - lo) / 2L;

			if (runFlow(mi, sh, P) >= needed)
				hi = mi;
			else lo = mi;
		}
		System.out.println(lo);
	}

	public static long runFlow(long maxDist, Shelter[] s, int[] P) {
		int ns = s.length;
		int nsubs = 1 << ns;
		FF graph = new FF(ns + nsubs + 2);

		int vsrc = ns + nsubs, vsink = vsrc + 1;

		for (int i = 0; i < ns; i++)
			graph.addEdge(vsrc, i, s[i].cap);

		for (int i = 0; i < ns; i++)
			for (int j = 0; j < nsubs; j++)
				if ((j & (1 << i)) != 0)
					graph.addEdge(i, ns + j, Long.MAX_VALUE);

		long[] sums = new long[nsubs];
		for (int i = 0, n = P.length; i < n; i++) {
			int k = 0;
			for (int j = 0; j < ns; j++)
				if (s[j].dist[i] < maxDist)
					k |= 1 << j;
			sums[k] += P[i];
		}

		for (int i = 0; i < nsubs; i++)
			graph.addEdge(ns + i, vsink, sums[i]);

		return graph.maxflow(vsrc, vsink);
	}

	public static class FFEdge {
		int to, rev;
		long cap, flow;

		public FFEdge(int to, int rev, long cap) {
			this.to = to;
			this.rev = rev;
			this.cap = cap;
			this.flow = 0;
		}
	}

	public static class FF {
		int n;
		ArrayList<FFEdge>[] G;

		public FF(int n) {
			this.n = n;
			G = (ArrayList<FFEdge>[]) new ArrayList[n];
			for (int i = 0; i < n; i++)
				G[i] = new ArrayList<FFEdge>();
		}

		public void addEdge(int u, int v, long c) {
			G[u].add(new FFEdge(v, G[v].size(), c));
			G[v].add(new FFEdge(u, G[u].size() - 1, 0));
		}

		public long bfs(int s, int t) {
			ArrayList<Integer> q = new ArrayList<Integer>();
			int[] prev = new int[n];
			boolean[] seen = new boolean[n];
			int qs = 0;
			q.add(s);
			seen[s] = true;
			while (qs < q.size()) {
				int v = q.get(qs++);
				for (FFEdge e : G[v])
					if (!seen[e.to] && e.flow < e.cap) {
						seen[e.to] = true;
						prev[e.to] = e.rev;
						q.add(e.to);
					}
			}

			if (!seen[t]) return 0L;

			// trace back the path
			long mf = Long.MAX_VALUE;
			for (int v = t; v != s; ) {
				int w = G[v].get(prev[v]).to, r = G[v].get(prev[v]).rev;
				mf = Math.min(mf, G[w].get(r).cap - G[w].get(r).flow);
				v = w;
			}

			for (int v = t; v != s; ) {
				int w = G[v].get(prev[v]).to, r = G[v].get(prev[v]).rev;
				G[w].get(r).flow += mf;
				G[v].get(prev[v]).flow -= mf;
				v = w;
			}
			return mf;
		}

		long maxflow(int s, int t) {
			long f = 0, df = 0;
			while ((df = bfs(s, t)) > 0) f += df;
			return f;
		}
	}
}