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

public class LudoRealDinic {

	/* Class for a little more than slow input reading */
	public static class Kattio extends PrintWriter {

		public Kattio(InputStream i) {
			super(new BufferedOutputStream(System.out));
			r = new BufferedReader(new InputStreamReader(i));
		}
		public Kattio(InputStream i, OutputStream o) {
			super(new BufferedOutputStream(o));
			r = new BufferedReader(new InputStreamReader(i));
		}

		public boolean hasMoreTokens() {
			return peekToken() != null;
		}

		public int getInt() {
			return Integer.parseInt(nextToken());
		}

		private BufferedReader r;
		private String line, token;
		private StringTokenizer st;

		private String peekToken() {
			if (token == null)
				try {
					while (st == null || !st.hasMoreTokens()) {
						line = r.readLine();
						if (line == null) return null;
						st = new StringTokenizer(line);
					}
					token = st.nextToken();
				} catch (IOException e) { }
			return token;
		}

		private String nextToken() {
			String ans = peekToken();
			token = null;
			return ans;
		}
	}

	public static Kattio kt;
	public static int read() { return kt.getInt(); }
	public static final int MAXN = 100 * 1000;
	public static final int MAXS = 10;

	public static void main(String[] args) throws IOException {
		long time_start = System.nanoTime();
		kt = new Kattio(System.in);

		// all zero based
		int N = read(), M = read(), S = read();

		int[] cap = new int[MAXN];
		for (int i = 0; i < N; i++) cap[i] = read();

		ArrayList<FwEdge>[] graph = (ArrayList<FwEdge>[]) new ArrayList[N];
		for (int i = 0; i < N; i++) 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));
		}

		int[] s = new int[S], scap = new int[S];
		for (int i = 0; i < S; i++) {
			s[i] = read() - 1;
			scap[i] = read();
		}

		long time_input_done = System.nanoTime();

		long[][] dist = new long[S][MAXN];
		for (int i = 0; i < S; i++) {
			Arrays.fill(dist[i], Long.MAX_VALUE);
		}

		PriorityQueue<Relax> pq = new PriorityQueue<Relax>(1,
			(a, b) -> ((Long) a.relaxDist).compareTo(b.relaxDist)
		);

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

		long time_dijkstra_done = System.nanoTime();

		long need = 0;
		for (int i = 0; i < N; i++) need += cap[i];
		int nsubs = 1 << S, source = S + nsubs, sink = source + 1;
		Dinic flow = new Dinic(S + nsubs + 2, source, sink);

		/*
		long[] D = new long[S * N];
		for (int i = 0; i < S; i++)
			for (int j =0 ; j < N; j++)
				D[i * N + j] = dist[i][j];
		Arrays.sort(D);

		ArrayList<Long> unique = new ArrayList<Long>();
		long lst = -1;
		for (long l : D) {
			if (l != lst) unique.add(l);
			lst = l;
		}

		for (long i : unique) {
			System.err.println("Distance: " + i);
		}*/

		// int lo = -1, hi = unique.size() - 1;
		long maxdist = 0;
		for (int i = 0; i < S; i++) for (int j = 0; j < N; j++) maxdist = Math.max(maxdist, dist[i][j]);
		long lo = -1, hi = maxdist;
		while (hi - lo > 1L) {
			long bs_start = System.nanoTime();

			long mi = (lo + hi) / 2;

			flow.resetGraph();
			for (int i = 0; i < S; i++)
				flow.addEdge(source, i, scap[i]);

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

			long[] sums = new long[1 << S];
			for (int i = 0, n = cap.length; i < n; i++) {
				int k = 0;
				for (int j = 0; j < S; j++)
					// if (dist[j][i] <= unique.get(mi))
					if (dist[j][i] <= mi)
						k |= 1 << j;
				sums[k] += cap[i];
			}

			for (int i = 0; i < (1 << S); i++)
				flow.addEdge(S + i, sink, sums[i]);

			if (flow.maxflow(source, sink) >= need)
				hi = mi;
			else
				lo = mi;

			long bs_end = System.nanoTime();

			System.err.println("Binary search D = " + mi + " took " + ((bs_end - bs_start) / 1000000) + " ms");
		}

		long time_done = System.nanoTime();

		// System.out.println(unique.get(hi));
		System.out.println(hi);

		System.err.println(
			"TIMING:\nReading input: \t" + (time_input_done - time_start)/1000 +
			"µs\nDijkstra: \t" + (time_dijkstra_done - time_input_done)/1000 +
			"µs\nBinary search: \t" + (time_done - time_dijkstra_done)/1000
			+"µs"
		);
	}

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

	public static class Relax {
		public int to;
		public long relaxDist;

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

	public static class DinicEdge {
		public int to;
		public long cap, flow;

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

	public static class Dinic {
		int n, source, sink;
		int[] H, P;
		ArrayList<DinicEdge> G;
		ArrayList<Integer>[] E;

		public Dinic(int n, int source, int sink) {
			this.n = n;
			this.source = source;
			this.sink = sink;
			H = new int[n];
			P = new int[n];
			G = new ArrayList<DinicEdge>();
			E = (ArrayList<Integer>[]) new ArrayList[n];
			for (int i = 0; i < n; i++)
				E[i] = new ArrayList<Integer>();
		}

		public void resetGraph() {
			G.clear();
			for (int i = 0; i < n; i++) E[i].clear();
		}

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

		public long dfs(int t, int v, long mf) {
			if (v == t || mf == 0) return mf;
			for ( ; P[v] < E[v].size(); P[v]++) {
				int idx = E[v].get(P[v]);
				DinicEdge e = G.get(idx);
				if (H[e.to] != H[v] + 1) continue;

				long df = this.dfs(t, e.to, Math.min(mf, e.cap - e.flow));
				if (df > 0) {
					G.get(idx).flow += df;
					G.get(idx ^ 1).flow -= df;
					return df;
				}
			}
			return 0;
		}

		public long maxflow(int s, int t) {
			long f = 0, df = 0;
			while (true) {
				Arrays.fill(H, 0);
				H[s] = 1;

				ArrayList<Integer> q = new ArrayList<Integer>();
				int qs = 0;
				q.add(s);
				while (qs < q.size()) {
					int v = q.get(qs++);
					for (int i : E[v]) {
						int w = G.get(i).to;
						if (H[w] == 0 && G.get(i).flow < G.get(i).cap) {
							H[w] = H[v] + 1;
							q.add(w);
						}
					}
				}
				if (H[t] == 0) return f;
				Arrays.fill(P, 0);
				while ((df = this.dfs(t, s, Long.MAX_VALUE)) > 0) f += df;
			}
		}
	}
}