**Problem Description**

**Input**

The first line of input is the number of testcases.

The first line of each testcase contains three integers: N,M,K.

Then M lines contains u,v,w means between node u and node v has a edge, which distance is w.

T <= 5

2<= n <= 50000

1 <= k <= m <=100000

1<= k <=12

Each edge with a positive distance no more than 100000.

It is guaranteed the graph is connected.

**Output**

For each testcase, output one line with a integer: the shortest distance of the needed path.

**Sample Input**

1 3 4 2 2 3 5 2 2 10 1 2 1 3 1 4

**Sample Output**

20

**Hint**

The path is 1->2->2->3->1, which total distance is 20.

**Source**

2019绍兴市计算机技能竞赛