### 2009 Canadian Computing Competition, Stage 1

## 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 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.

### 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 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

Output the minimal total cost of purchasing a pencil on-line 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

All Submissions

Best Solutions

**Point Value:** 15

**Time Limit:** 5.00s

**Memory Limit:** 256M

**Added:** May 11, 2009

**Languages Allowed:**

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

## Comments (Search)

MongolianPoormanon Jan 15, 2016 - 4:35:01 am UTC Different Runtimebbi5291on Jan 15, 2016 - 7:16:35 am UTC Re: Different RuntimeButaneon Oct 17, 2014 - 12:11:24 am UTC Test case bugAlexon Oct 17, 2014 - 12:38:00 am UTC Re: Test case bugjavicon Feb 27, 2009 - 10:33:57 pm UTC wow nicejavicon Feb 27, 2009 - 10:29:33 pm UTC mehSaravannanon Feb 26, 2009 - 11:42:29 pm UTC Different scores?hansonw1on Feb 27, 2009 - 12:03:55 am UTC Re: Different scores?