Problem J

Toll Management II

The country of Byteland is in a mess, because of the rule of a mad king. He is forcing his peculiar decisions on the people of the country. One of his peculiar decisions is the toll management of the road system.

The country consists of N cities and M bidirectional roads, each connecting two cities. Anyone who crosses a road has to pay a predefined toll for that road.

The mad king has fixed the lowest toll for each path from the capital to other cities and vice versa, that is, one has to pay exactly P_i toll to go from capital to the i-th city if he chooses to travel in lowest possible total toll. But the predefined toll system of the country might not be consistent with it. That’s why the mad king is angry with the chief judge. The mad king will not change the lowest toll P_i. So the chief judge has to adjust the toll of each road such that it becomes consistent with the king’s decision. The adjusted toll of any road should not be negative.

As the chief judge is a poor programmer, he wants your help to write a program to adjust the toll of each road. But as per unit adjustment of toll in any road will cost the judge a unit payment, he wants the total adjustment in minimum cost, that is sum of absolute difference between actual and adjusted toll of each road is as minimum as possible.

Input

Input starts with an integer, T (T ≤ 20) denoting the number of test cases. Each case starts with two integers, N (1 ≤ N ≤ 10,000) and M (0 ≤ M ≤ 100,000). Next line contains N integers P_i (0 ≤P_i≤1,000,000), denoting the lowest toll from source to i-th city (0 ≤ i < N). Each of the next M lines contains three integers u, v (0 ≤ u,v < N, u ≠ v) and w (0≤w≤1,000,000) meaning that there is a bidirectional road between city u and v and the toll of the road is w units. No road will be mentioned more than once. City indexed 0 is the capital of Byteland.

Output

For each case, print the test case number, starting from 1. If there is no way to adjust the toll system that supports the king’s decision then output “Bad King”. Otherwise, print minimum total adjustment of the tolls in the existing toll system.

Sample Input

Output for Sample Input

3 3

0 3 5

0 1 2

1 2 3

0 2 2

3 3

0 3 5

0 1 2

1 2 3

0 2 7

Case 1: 4

Case 2: 2

Problemsetter: Shiplu Hawlader

Special Thanks: Md. Mahbubul Hasan