文理学院程序设计在线练习


Big Bridge

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 0   Accepted Submission(s): 0
Problem Description

City A can be seen as an undirected graph which includes N nodes and M edges. Each edge connects two nodes with a positive distance. There are K big bridges among edges. Xiaoxi has huge interests to them so she hopes you can design a shortest path which from node 1, through all k big bridges (pass every big bridge once at least), and finally return to node 1.

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绍兴市计算机技能竞赛