Canadian Computing Competition: 2009 Stage 1, Senior #4

In Doubleclickland, there are \(N\) cities \((2 \le N \le 5\,000)\) , with each city having various trade routes to other cities. In total, there are \(T\) trade routes \((1 \le T \le 5\,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) \le 10\,000\) and \(C(x, y) = C(y, x)\) . Out of the \(N\) cities, \(K\) \((1 \le K \le N)\) of these cities have stores with really nice pencils that can be purchased online. The price for each pencil in city \(x\) is \(P_x\) \((0 \le P_x \le 10\,000)\) .

Find the minimal price to purchase one pencil online and have it shipped to a particular city \(D\) \((1 \le D \le 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.

Input Specification

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 online. The next \(K\) lines contain 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 Specification

Output the minimal total cost of purchasing a pencil online and shipping it to city \(D\) .

Sample Input

3
3
1 2 4
2 3 2
1 3 3
3
1 14
2 8
3 3
1

Sample Output

6