##### Canadian Computing Competition: 2009 Stage 1, Senior #4

In Doubleclickland, there are cities , with each city having various trade routes to other cities. In total, there are trade routes in Doubleclickland. For each trade route between two cities and , there is a transportation cost to ship between the cities, where , and . Out of the cities, of these cities have stores with really nice pencils that can be purchased online. The price for each pencil in city is .

Find the minimal price to purchase one pencil online and have it shipped to a particular city using the cheapest possible trade-route sequence. Notice that it is possible to purchase the pencil in city and thus require no shipping charges.

#### Input Specification

The first line of input contains , the number of cities. You can assume the cities are numbered from to . The second line of input contains , the number of trade routes. The next lines each contain 3 integers, , , , to denote the cost of using the trade route between cities and is . The next line contains the integer , the number of cities with a store that sells really nice pencils online. The next lines contain two integers, and , to denote that the cost of a pencil in city is . The last line contains the integer , the destination city.

#### Output Specification

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

#### Sample Input

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

#### Sample Output

`6`

CCC problem statements in large part from the PEG OJ

## Comments

Since the original data were weak, an additional test case was added, and all submissions were rejudged.

So... you're telling me I have to pay up to $10000 for a pencil. And then pay to get it shipped. And then wait for it to be shipped across potentially thousands of cities.

... no thanks

how good would a "really nice pencil" have to be to cost that much

can a city have several prices for a pencil?

It shouldn't matter.

Is it guaranteed that it is possible to successfully ship a pencil to your city?

Yes

Is my algorithm too slow or a problem with the judge?

Your algorithm is suboptimal, and this problem is particularly strict with time limits.

What's the fastest way to store all the input in Python? I am TLEing even before i get all the trade routes processed on cases 4 and 5. I've tried using both lists and dictionaries, but they aren't working fast enough.

otherwise, storing the graph in an adjacency matrix represented by python

listsshould be fineThanks a lot. Using dictionaries is a lot slower for some reason.

Fast input is required for this problem.

Here is a macro for C++ that reads an unsigned integer much faster than scanf:

Thank you so much :D

How does that work? Is there any special meaning to the "char _;"?

it's a char named _