Migrated from Lutece 1482 桃花源记

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

陶渊明（365-427）是东晋诗人。他最著名的作品之一是《桃花源记》。在中国，“桃花源”是指“乌托邦”。

在“桃花源”的故事中，有一个神秘的地方。在秦时，有些村民逃到那个地方，在动乱时期建立了一个村庄。他们和他们的后代从未离开过，也从未接触过外面的世界，从那时起，直到几个世纪后，一个渔民发现他们。

最近，一些电子科大基佬们碰巧发现了文中提到的“桃花源”。

他们还发现了一份有关“桃花源”的房屋的文件。该文件说：

村里有$n$个房子和$m$条路。每条路连着两个房子。这些房子从$1$到$n$进行编号。有$k$个家庭生活在这里，每个家庭都住在不同的房子里。

他们住的房子是$1$号，$2$号，…，$k$号。还有$k$个破烂的房子：$n-k+1$号,$n-k+2$号，…，$n$号。破烂的房子有暗室,可以作为躲藏秦军的地方。

问题是，所有的道路都被破坏了。人们想修多条路，使每个家庭都能通过修好的道路到达一个破烂的房子。每一个破烂的房子只能容纳一个家庭。每一条路都要花费一些费用去修理。村长想找出最小的成本但他不知道怎么做。

你能解决古村落的问题吗？

Input

输入的开始有一行包含一个整数$T(1<=T<=10)$表示事件数量。

对于每一个事件下，第一行三个整数$n(4<=n<=50)$，$m（0<=m<=1000)$和$k(1≤k≤5,2k<=n)$。

然后有$m$行，每一个包含三个整数，$u$，$v$和$w$，表明有一个破坏的道路,该道路连着$u$,$v$，维修的成本是$w(1<=w<=1000)$。

Output

对于每一个事件输出占一行，如果你无法找到一个合适的方法来修复道路，输出一个字符串“No solution”。否则，输出最低成本。

Samples

2
4 3 1
4 2 10
3 1 9
2 3 10
6 7 2
1 5 1000
2 6 1000
1 3 1
2 3 1
3 4 1
4 5 1
4 6 1

29
5

Resources

每周一题 div1