## Problem S4: 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 Px (0 ≤ Px ≤ 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.

### Input

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 Pz, to denote that the cost of a pencil in city z is Pz. The last line contains the integer D, the destination city.

### Output

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

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

### Sample Output

`6`

Point Value: 15
Time Limit: 5.00s
Memory Limit: 256M

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

• (0/0)
How come solutions that didn't meet the runtime requirement were accepted?

• (0/0)
the time limit is per test case

• (1/0)
Test case 1 has some cities that are numbered N+1 which does not satisfy the problem's constraints.

• (0/0)
Sorry for the inconvenience. This has been fixed, and all affected solutions were rejudged.

• (1/0)
mem limit 1024MB XDD

• (0/0)
data not fully updated yet... but who cares anyway xD

• (0/0)
When Hanson submitted my solution I got 0/50 but when I submit the same solution I get 10/50?

• (0/0)
The CCC official data had a bug in it, but your program passes that case now. (You'll get 3 more points!)