Minimum Travel Cost with Toll Booths and Fuel Station

You are given a network of n intersections and m bidirectional roads. Each road connects two intersections and has a travel time. Some intersections have toll booths with an associated toll fee. However, there is a fuel station located at one of the intersections where the toll charge is waived.

Your task is to compute the minimum travel cost from intersection 1 to intersection n. The cost of a route is the sum of travel times for the roads taken, and if you pass an intersection with a toll booth (other than the fuel station), the toll fee will be added to the total cost.

The problem can be formulated as follows: Given a graph \(G=(V,E)\) with \(|V| = n\) nodes and \(|E| = m\) edges, where each edge \((u,v)\) has a weight \(w\). For some nodes the toll fee \(t\) is applied if the node is visited, except if the node is the designated fuel station \(f\). Find the minimum cost path from node 1 to node n.

inputFormat

The input is given from standard input (stdin) as follows:

n m
u1 v1 w1
u2 v2 w2
... (m lines in total)
T
[ toll_booth1 toll_booth2 ... toll_boothT ]
[ toll_amount1 toll_amount2 ... toll_amountT ]
fuel_station

Here, the first line contains two integers, n and m, where n is the number of intersections and m is the number of roads. The next m lines each contain three integers u, v, and w, indicating a bidirectional road between intersections u and v with travel time w. Then an integer T is given, representing the number of toll booths. The following line contains T integers representing the intersections with toll booths (if T is 0, this line will be empty). The next line contains T integers representing the toll fee for each corresponding toll booth (if T is 0, this line will be empty). The final line contains a single integer indicating the intersection that has the fuel station (where the toll is not charged).

outputFormat

Output a single integer to standard output (stdout): the minimum travel cost from intersection 1 to intersection n.

## sample

5 6
1 2 2
1 3 2
2 4 3
3 4 3
4 5 1
3 5 2
2
2 4
3 5
3

4

</p>