# Budget Travelling
## Problem Statement
You are planning a trip to the country of Wonderland, which consists of $N$ cities. Not all cities are directly connected by roads, but you have a map detailing all existing roads and their lengths. You arrive at city $A$ and your goal is to reach city $B$.
You have booked a car, but its fuel tank is initially empty. The car's fuel tank has a maximum capacity of $C$ liters. You know the cost per liter of petrol in each city. To travel one unit of distance, your car consumes one liter of petrol.
Your task is to find the minimum total cost to travel from city $A$ to city $B$. You can buy any integer amount of petrol up to the tank's capacity in any city you visit.
It is guaranteed that it is always possible to reach city $B$ from city $A$.
## Input Format
- The first line contains a single integer $N$ ($1 \le N \le 10000$) - the number of cities in Wonderland.
- The second line contains a single integer $M$ ($1 \le M \le 100000$) - the number of roads in the country.
- The next $M$ lines each describe a road, containing three integers $u$, $v$, and $d$: there is a bidirectional road between city $u$ and city $v$ of length $d$. ($1 \le u, v \le N$, $u \ne v$, $1 \le d \le C$).
- The next line contains $N$ space-separated integers $P_1, P_2, \dots, P_N$, where $P_i$ is the per liter cost of petrol in city $i$. ($1 \le P_i \le 100$).
- The last line contains three integers $A$, $B$, and $C$: $A$ is the starting city, $B$ is the destination city, and $C$ is the capacity of the car's petrol tank. ($1 \le A, B \le N$, $A \ne B$, $1 \le C \le 100$).
## Output Format
Print a single integer representing the minimum cost to reach city $B$ from city $A$.
## Sample Test Cases
### Sample Input 1
```
5
5
1 2 1
2 3 1
3 4 1
4 5 1
1 4 6
1 10 10 10 1
1 5 8
```
### Sample Output 1
```
4
```
### Sample Input 2
```
6
6
1 2 1
2 3 1
3 4 1
4 5 1
1 6 1
6 5 5
10 10 10 10 1 1
1 5 8
```
### Sample Output 2
```
15
```
## Constraints
- $1 \le N \le 10000$
- $1 \le M \le 100000$
- $1 \le C \le 100$
- $1 \le u, v \le N$, $u \ne v$
- $1 \le d \le C$
- $1 \le A, B \le N$, $A \ne B$
- $1 \le P_i \le 100$
- Time limit: 10 seconds
- Memory limit: 256 MB
## Explanation
### Sample 1
Starting in city $1$ with a tank capacity of $C=8$. The cheapest path to city $5$ is $1 \to 2 \to 3 \to 4 \to 5$. The total distance is $1+1+1+1=4$. The cost of petrol in city $1$ is $P_1=1$. You can buy $4$ liters of petrol in city $1$ for a total cost of $4 \times 1 = 4$. Since $4 \le C=8$, this is possible. You then travel along the path $1 \to 2 \to 3 \to 4 \to 5$ to reach city $5$.
### Sample 2
Starting in city $1$ with a tank capacity of $C=8$. The direct path $1 \to 2 \to 3 \to 4 \to 5$ requires $4$ liters of petrol. The cost in city $1$ is $P_1=10$. This would cost $40$. A cheaper alternative is to buy $1$ liter in city $1$ (cost $10 \times 1 = 10$) and travel to city $6$. From city $6$, you need to travel to city $5$. The road from $6 \to 5$ has length $5$. The cost of petrol in city $6$ is $P_6=1$. You can buy $5$ liters in city $6$ (cost $1 \times 5 = 5$). The total cost is $10 + 5 = 15$.
Loading problem statement...