题目描述

Jones 实现了他的梦想：他加入了国际空间站（ISS）的一次任务。他接受了他的第一个任务：检查空间站上的电子设备的工作状况。

ISS 被分为 $N$ 个模块，模块从 $1$ 到 $N$ 编号。Jones 发现，为了提高效率，空间站的设计使任意两个模块之间仅存在一条简单路径。在一次太阳耀斑活动中，连接两个模块的双向通道很容易受到辐射影响。检查一条通道 $i$ 的状况必须花费 $C_i$ 的时间。Jones 需要找到一条从模块 $1$ 出发，经过每条通道至少一次，再回到模块 $1$ 的最快路径。

除了从模块之间的通道中通过之外，Jones 还可以穿上宇航服，跳出空间站，从外面直接从某一模块移动到任意模块上，但是这种方法只能进行最多 $M$ 次。Jones 假设进行一次需要花费固定的时间 $K$。

输入格式

第一行包含一个整数 $T$，代表测试组数。

每个测试组中，第一行包含三个整数 $N, M, K \ (1 \leq N, M \leq 1000)$，接下来 $N-1$ 行每一行包含三个整数 $A, B, C \ (1 \leq A \leq B \leq N; 0 \leq C,K \leq 10^6)$，代表在模块 $A$ 和 $B$ 之间有一条通道，检查它需要花费 $C$ 时间。

输出格式

对于每一组测试数据，输出一行答案。

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

12
33