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

public class LudoDinicFlow {

	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 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;
		Dinic graph = new Dinic(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 DinicEdge {
		int to, rev;
		long cap, flow;

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

		public long residual() {
			return this.cap - this.flow;
		}

		public boolean saturated() {
			return this.residual() <= 0;
		}
	}

	public static class Dinic {
		int H[];
		ArrayList<DinicEdge>[] G;

		public Dinic(int n) {
			H = new int[n];
			G = (ArrayList<DinicEdge>[]) new ArrayList[n];
			for (int i = 0; i < n; i++)
				G[i] = new ArrayList<DinicEdge>();
		}

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

		public void bfs(int s) {
			for (int i = 0, n = H.length; i < n; i++)
				H[i] = 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 (DinicEdge e : G[v])
					if (H[e.to] == 0 && e.flow < e.cap) {
						H[e.to] = H[v] + 1;
						q.add(e.to);
					}
			}
		}

		public long dfs(int t, int v, long mf) {
			if (v == t) return mf;
			long f = 0L;
			boolean sat = true;
			for (int i = 0, n = G[v].size(); i < n; i++) {
				DinicEdge e = G[v].get(i);
				if (H[e.to] != H[v] + 1 || e.saturated())
					continue;
				long df = this.dfs(t, e.to, Math.min(mf - f, e.residual()));
				f += df;
				G[v].get(i).flow += df;
				G[e.to].get(G[v].get(i).rev).flow -= df;
				sat &= G[v].get(i).residual() == 0;
				if (mf == f) break;
			}
			if (sat) H[v] = 0;
			return f;
		}

		public long augment(int s, int t) {
			this.bfs(s);
			return H[t] != 0 ? this.dfs(t, s, Long.MAX_VALUE) : 0;
		}

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