Collect Jewel
题号：NC15331
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

There is a mystical country on the magic continent.
There are N jewel caves and M directed roads connecting these caves in the country. The caves are numbered from 1 to N, and the ith cave has Ai jewels. The roads are numbered from 1 to M, the ith road connects the cave from Ui to Vi.

The King loves jewel very much, so he wants to dispatch no more than K soldiers to the jewel caves to collect jewels.

Firstly, the King will give each soldier a unique route. Then, each soldier will be transferred to the starting point of his unique route. And they will follow the route to collect the jewels until they arrive at the end of the route. Finally, they will go back to the King by air and give all the jewels they collected to the King.

After a soldier arrives at a jewel cave, he will take all the jewels in the cave away. However, because of the harassment of the robbers in the route, when the soldier passes through the ith road he will pay Ci jewels to the robbers. At any time, the number of jewels on the soldier could be zero and even negative.

Please help the King setting up routes for every soldier to collect jewels as much as possible.


输入描述:

The first line contains an integer T, where T is the number of test cases. T test cases follow.
For each test case, the first line contains three integers N, M and K, where N is the number of jewel caves, M is the number of roads and K is the number of soldiers that the King could dispatch at most. 
The second line contains N integers A1, A2, ... , AN, where Ai is the number of jewels in the ith cave.
Then M lines followed, each line contains three integers Ui, Vi and Ci, indicating there is a road connectsthe cave from Ui to Vi and when the soldiers pass through the road he should pay Ci jewels.
• 1 ≤ T ≤ 10.
• 1 ≤ N ≤ 102.
• 0 ≤ M ≤ 103.
• 1≤ K ≤105
• 0≤ Ai,Ci ≤104. 
• 1 ≤ Ui < Vi ≤ N.

输出描述:

For each test case, print one line containing “Case #x: y”, where x is the test case number (starting from
1) and y is the largest number of jewels the King could get.
示例1

输入

复制 
2
2 1 1
3 4
1 2 2
4 5 2
5 6 2 3
1 2 1
1 3 2
2 3 3
1 4 4
3 4 5

输出

复制 
Case #1: 5
Case #2: 13

备注:

For the first case, the King will dispatch 1 soldier. Soldier 1 will follow the route {1 → 2}.

For the second case, the King will dispatch 2 soldiers. Soldier 1 will follow the route {1 → 2}. Soldier 2will follow the route {4}.