## TLE '16 Contest 6 (Mock CCC) S5 - Toll Routes

Fax McClad, Croneria's most profitable bounty hunter, has a part-time job delivering microwaves.

Croneria has cities - numbered from to . toll routes connect the cities. The toll route costs Cronerian Moneys to travel on and allows a one-way connection from city to city . An interesting thing to note about the Cronerian Toll Route system is that it is impossible to visit the same city twice on a single trip, even though all outgoing connections are usable.

However, the Committee for Charging Cronerians (CCC), the organization responsible for setting the tolls on the toll route system, is greedy. At times, they might decide to add an integer amount to the cost of every single toll route. In order to trick Cronerians into thinking they are fair, the CCC might add a negative amount to the costs.

days will pass. On the day, Fax needs to deliver microwaves from city to customers in city and the CCC adds moneys to the cost of every single toll route.

For each day, can you tell Fax the minimum amount of moneys he will need to spend to deliver the microwaves?

#### Input Specification

The first line of input will contain 3 space-separated integers, , , and .

lines of input follow. The line will contain 3 space-separated integers, , , and , specifying the toll route.

lines of input follow. The line will contain 2 space-separated integers, and . The absolute value of the total change from any toll route's initial cost will not exceed .

For 1 of the 15 points, each city has at most 1 out-going toll route and .

For an additional 2 of the 15 points, and the cost of any toll route will always be non-negative.

For an additional 2 of the 15 points, .

For an additional 2 of the 15 points, .

#### Output Specification

For each day, print the minimum amount of moneys Fax needs to spend to reach his destination. If no path exists, print `Cannot Deliver`

.

#### Sample Input

```
5 6 3
1 2 2
2 5 4
1 5 10
1 3 2
3 4 3
4 5 4
0 5
10 5
-20 5
```

#### Sample Output

```
6
20
-21
```

#### Explanation for Sample Output

On the first day, no changes were made to the toll routes, so Fax should take the path for a minimal cost of 6.

On the second day, the cost of each toll route increased by 10, so Fax should take the path for a minimal cost of 20.

On the third day, the cost of each toll route decreased by 20, so Fax should take the path for a minimal cost of -21.

## Comments