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

## Comments

Is it guaranteed that there is only 1 undirected trade route between 2 cities?

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

This comment is hidden due to too much negative feedback. Show it anyway.

This comment is hidden due to too much negative feedback. Show it anyway.

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 _