Crossing all the hurdles, Gudi now reaches the roof of the castle and she finds Puchi, the Lord of Azkahar and the Protector of the castle, waiting for her. After having been through the stages in the castle, Gudi has had a change of heart and no longer wants the treasure. Instead, she expresses her desire to become the Lady of Azkahar. However, the position of the Lady can not be won that easily. Puchi decides to take a final test.
He weaves his magic and N Islands, spread across a vast sea , appear before them. He goes on the say :
The Lady needs to rule the masses and take important decisions. Let us see how well can you do that. These are N Islands, indexed from 1 to N. There are M bidirectional roads in total, wherein each road connects 2 distinct Islands and multiple roads may connect a pair of Islands. Each of the first K Islands i.e. Islands with index from 1 to K, have a soldier who fought valiantly in the battle and wants to get to a shelter. Each of the last K Islands i.e. Island with index from N−K+1 to N, have a shelter home that can house only 1 Soldier.
These soldiers await your commands. The cost effort of reaching a shelter for a soldier is the distance that has to be traveled. In addition, you have the option of using magic to transport the soldiers. One use of magic will allow you to move any solider from any island to any other island. Using your magic once costs 104 units of effort. You can always use your magic, but then again it comes at a huge cost. Give a target shelter to each of the soldiers and minimize the overall cost efforts of the scenario.
Help Gudi find the minimum cost efforts.
Input
First line contains an integer T.T testcases follow.
Each testcase consists of 3 space-separated integers N, M and K. M lines follow.
Each of these lines, contains 3 integers X, Y and C, denoting that there is a road between Island X and Island Y of distance C units.
Output
Print the answer to each testcase in a new line.
Constraints
1≤T≤10
1≤K≤80
2K+1≤N≤200
1≤M≤1000
1≤X,Y≤N
1≤C≤1000
For the testcases, Soldiers on Island 1,2 and Shelters on Island 5,6.
In the first testcase, the soldier on Island 1 can travel to Island 5 with cost=2 and the soldier on Island 2 can travel to Island 6 with cost = 2. Hence, total cost=4.
In the second testcase, the soldier on Island 1 can travel to Island 6 with cost=3 and the soldier on Island 2 has to be transported magically to Island 5 with cost= 10000, thereby total cost= 10003
