You, a programmer of an important software house, have been fired because you didn't solve an important problem that was assigned to you. You are very furious and want to take revenge on your boss, breaking the communication between his computer and the central server.

The computer of your boss and the central server are in the same network, which is composed of many machines (computers) and wires linking pairs of those machines. There is at most one wire between any pair of machines and there can be pairs of machines without a wire between them.

To accomplish your objective, you can destroy machines and wires, but you can't destroy neither the computer of your boss, nor the central server, because those machines are monitored by security cameras. You have estimated the cost of blowing up each machine and the cost of cutting each wire in the network.

You want to determine the minimum cost of interrupting the communication between your boss' computer and the central server. Two computers A and B can communicate if there is a sequence of undestroyed machines x₁, x₂, ..., x_n such that x₁ = A, x_n = B and x_i is linked with x_i+1 with an uncut wire (for each 1 ≤ i < n).

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with two integers M (2 ≤ M ≤ 50) and W (0 ≤ W ≤ 1200) where M denotes the number of machines and W denotes the number of wires. The ids of the boss' machine and the server are 1 and M respectively. The next line contains M - 2 integers denoting the cost for destroying the machines from 2 to M - 1 respectively. Each of the next W lines contains three integers i j c, meaning that the wire between machine i and j can be destroyed with the cost of c. All the destroying costs are between 0 and 10⁵.

For each case, print the case number and the minimum cost of interrupting the communication between the computer of your boss and the central server.