import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Invasion_Slow_Hall {

	
	static class Location
	{
		long dist;
		int index;
		Location(long d, int i)
		{
			dist = d;
			index = i;
		}
	}
	
	static class Edge
	{
		long length;
		int dest;
		Edge(long l, int d)
		{
			length = l;
			dest = d;
		}
	}
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); //Houses.
		int m = sc.nextInt(); //Roads.
		int s = sc.nextInt(); //Shelters.
		
		long[][] dists = new long[s][n]; // This stores the distances from the shelters to the houses.
		int[] positions = new int[s];
		long[] capacities = new long[s];
		long[] people = new long[n];
		
		for(int i = 0; i < s; i++)
			for(int j = 0; j < n; j++)
				dists[i][j] = (long) 1e18;

		ArrayList<ArrayList<Edge>> edges = new ArrayList<ArrayList<Edge>>(n);
		for(int i = 0; i < n; i++)
			edges.add(new ArrayList<Edge>());

		for(int i = 0; i < n; i++)
			people[i] = sc.nextLong();
		
		for(int i = 0; i < m; i++)
		{
			int a = sc.nextInt();
			int b = sc.nextInt();
			--a; --b;
			long l = sc.nextLong();
			edges.get(a).add(new Edge(l, b));
			edges.get(b).add(new Edge(l, a));
		}

		for(int i = 0; i < s; ++i){
			positions[i] = sc.nextInt()-1;
			capacities[i] = sc.nextInt();
		}
		
		for(int i = 0; i < s; i++) // Dijkstra to find all distances
		{
			boolean[] visited = new boolean[n+s];
			PriorityQueue<Location> pq = new PriorityQueue<Location>((a,b) -> (int)Math.signum(a.dist - b.dist));
			
			pq.add(new Location(0, positions[i]));
			
			while(!pq.isEmpty())
			{				
				Location cur = pq.remove();
				if(visited[cur.index]) continue;
				visited[cur.index] = true;
				dists[i][cur.index] = cur.dist;
				
				for(Edge e: edges.get(cur.index))
					if(!visited[e.dest])
						pq.add(new Location(cur.dist + e.length, e.dest));
			}			
		}
		
		// Hall's Marriage theorem.
		long min_time = 0; // Inclusive.
		long max_time = (long) 1e18; // Exclusive.
		
		while(max_time - min_time > 0)
		{
			long time = (max_time + min_time) / 2;
			Boolean possible = true;
			
			for(int i = 0; i < (1 << s) && possible; i++) {
				long cap = 0;
				for(int j = 0; j < s; j++)
					cap += ((i >> j) & 1) * capacities[j]; 
				
				long needed = 0;
				// Check if this house is dependent on the currently considered shelters.
				for(int k = 0; k < n; k++) {
					Boolean dependent = true;
					for(int j = 0; dependent && j < s; j++){
						// If this house can go somewhere else, we ignore it. 
						if(((i >> j) & 1) == 0 && dists[j][k] <= time) dependent = false;
					}
					if(dependent) needed += people[k];
				}

				if(needed > cap) possible = false;// The current time is insufficient.
				
			}
			if(possible) max_time = time;
			else min_time = time+1;
		}
		
		System.out.println(min_time);
		
	}

}