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 on-line. The price for each pencil in city is .
Find the minimal price to purchase one pencil on-line 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.
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 on-line. The next lines contains two integers, and , to denote that the cost of a pencil in city is . The last line contains the integer , the destination city.
Output the minimal total cost of purchasing a pencil on-line and shipping it to city .
3 3 1 2 4 2 3 2 1 3 3 3 1 14 2 8 3 3 1
CCC problem statements in large part from the PEG OJ