Jones 实现了他最大的梦想之一：他被录取参加国际空间站（ISS）的下一次任务。他已经接到了他的第一个任务：检查空间站上所有电子元件的完整性。

ISS 由 $N$ 个模块组成，编号从 $1$ 到 $N$。Jones 发现，出于效率考虑，空间站的设计使得任意两个不同模块之间恰好存在一条简单路径。在太阳耀斑爆发时，连接两个不同模块的双向路段特别容易受到辐射。检查一个路段 $i$ 需要花费整数时间 $C_i$。自然地，Jones 试图找到一条最快的访问路径，该路径从模块 $1$ 出发，访问每个路段至少一次，并返回模块 $1$。

除了使用两个模块之间的直接路段外，Jones 还可以穿上太空服，在空间站外寻找任意两个模块之间的直接路径。然而，他最多只能执行 $M$ 次这样的操作。Jones 假设穿上太空服并使用它从一个模块跳跃到任何其他模块需要固定的时间 $K$。

输入格式

第一行包含数字 $T$，表示测试用例的数量。描述一个测试用例的第一行包含三个变量 $N, M, K$ ($1 \le N, M \le 1000$)。接下来的 $N-1$ 行格式为 $A \ B \ C$ ($1 \le A \le B \le N; 0 \le C, K \le 10^6$)，表示存在一条从 $A$ 到 $B$ 的直接路段，耗时为 $C$ 个时间单位。

输出格式

对于每个测试用例 $i$，在单独的一行上输出一个数字，表示该测试用例的答案。

样例

样例输入 1

2
5 2 4
1 2 2
2 3 2
1 4 2
4 5 2
7 2 0
1 2 1
1 3 5
2 4 10
2 5 1
5 6 10
5 7 5

样例输出 1

12
33