Pritam is a priest in his village. He needs to pay his respects to k shrines which his all ancestors have visited and had asked their successors to pay the respect. But he hates walking so he wants to minimize the distance he has to travel to pay his respects. As he is busy packing he asks you to help him. He has acquired a bunch of portal scrolls through which he can create portal networks. Portals can only be created at shrines , and after entering a portal a he can exit at any desired portal. You have to give the minimum distance Pritam has to travel. There are number of cities which don’t have shrines but that can be traveled through.
You will be given n the number of cities and out of which first k cities have shrines. There is road connecting two cities which will be defined by three integers a, b and c where a and b are the cities and c is the distance between the cities. You have to calculate the minimum distance that need to be walked for this pilgrimage given that there is no restriction on number of portals that can be created but need to be created at shrines. After you have told him the distance he’ll decide whether it’s worth undertaking or not. You can assume that he starts from 1st city.

[Input]
First line contains integer t denoting number of test cases.
First line of every test case consists of 3 integers n, m and k denoting number of cities, number of roads and number of shrines respectively.
Next m lines of test case consists of 3 space separated integers a, b and c, where a and b are cities and c is the distance between them.

[Output]
For each test case print a single integer containing the minimum distance he need to walk for the pilgrimage.

[Constraints]
1<=t<=20
1<=n<=100
n-1<=m<=(n*(n-1))/2
1<=k<=n
1<=a,b<=n
1<=c<=1000000