6817번 - Shop and Ship 다국어

In Doubleclickland, there are N cities (N ≤ 5, 000), with each city having various trade routes to other cities. In total, there are T trade routes (0 ≤ T ≤ 25, 000, 000). in Doubleclickland. For each trade route between two cities x and y, there is a transportation cost C(x, y) to ship between the cities, where C(x, y) ≥ 0, C(x, y) ≤ 10, 000 and C(x, y) = C(y, x). Out of the N cities, K (1 ≤ K ≤ N) of these cities have stores with really nice pencils that can be purchased on-line. The price for each pencil in city x is P_x (0 ≤ P_x ≤ 10, 000).

Find the minimal price to purchase one pencil on-line and have it shipped to a particular city D (1 ≤ D ≤ N) using the cheapest possible trade-route sequence. Notice that it is possible to purchase the pencil in city D and thus require no shipping charges.

The first line of input contains N, the number of cities. You can assume the cities are numbered from 1 to N. The second line of input contains T, the number of trade routes. The next T lines each contain 3 integers, x y C(x, y), to denote the cost of using the trade route between cities x and y is C(x, y). The next line contains the integer K, the number of cities with a store that sells really nice pencils on-line. The next K lines contains two integers, z and P_z, to denote that the cost of a pencil in city z is P_z. The last line contains the integer D, the destination city

Output the minimal total cost of purchasing a pencil on-line and shipping it to city D.