Fax McClad flying over a toll route while towing a microwave to be delivered.

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

Croneria has ~N~ cities - numbered from ~1~ to ~N~. ~M~ toll routes connect the cities. The ~i^\text{th}~ toll route costs ~t_i~ Cronerian Moneys to travel on and allows a one-way connection from city ~u_i~ to city ~v_i~. 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.

~D~ days will pass. On the ~j^\text{th}~ day, Fax needs to deliver microwaves from city ~1~ to customers in city ~d_j~ and the CCC adds ~c_j~ 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, ~N~ ~(1 \le N \le 3\,000)~, ~M~ ~(1 \le M \le 6\,000)~, and ~D~ ~(1 \le D \le 2 \times 10^6)~.

~M~ lines of input follow. The ~i^\text{th}~ line will contain 3 space-separated integers, ~u_i~, ~v_i~, and ~t_i~ ~(1 \le u_i, v_i \le N; u_i \ne v_i; -10^9 \le t_i \le 10^9)~, specifying the ~i^\text{th}~ toll route.

~D~ lines of input follow. The ~j^\text{th}~ line will contain 2 space-separated integers, ~c_j~ and ~d_j~ ~(1 \le d_j \le N)~. The absolute value of the total change from any toll route's initial cost will not exceed ~10^9~.

For 1 of the 15 points, each city has at most 1 out-going toll route and ~D \le 2 \times 10^5~.

For an additional 2 of the 15 points, ~N, M, D \le 100~ and the cost of any toll route will always be non-negative.

For an additional 2 of the 15 points, ~N, M, D \le 30~.

For an additional 2 of the 15 points, ~D \le 1\,000~.

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 ~1 \to 2 \to 5~ 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 ~1 \to 5~ 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 ~1 \to 3 \to 4 \to 5~ for a minimal cost of ~-21~.