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

public class LudoHall {

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

		public double getDouble() {
			return Double.parseDouble(nextToken());
		}

		public long getLong() {
			return Long.parseLong(nextToken());
		}

		public String getWord() {
			return nextToken();
		}



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

		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() {
		// might consider faster input
		return kt.getInt();
	}

	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 {
		kt = new Kattio(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 lo = 0, hi = Long.MAX_VALUE;
		while (hi - lo > 1L) {
			long mi = lo + (hi - lo) / 2L;

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

	public static boolean saturated(long maxDist, Shelter[] s, int[] P) {
		int ns = s.length;
		int nsubs = 1 << ns;

		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];
		}

		// subset convolution
		for (int b = 1; b < nsubs; b <<= 1) {
			for (int i = 0; i < nsubs; i++) {
				if ((i & b) == 0) sums[i | b] += sums[i];
			}
		}

		for (int i = 0; i < nsubs; i++) {
			long av = 0L;
			for (int j = 0; j < ns; j++)
				if ((i & (1 << j)) != 0)
					av += s[j].cap;
			if (av < sums[i])
				return false;
		}
		return true;
	}
}