SP21353 CLZDOUGH - Avantgarde and Doughnut

最近，Mr. Avantgarde 接到了一项送甜甜圈的任务，为此他借了一辆电动车。小镇上有 $N$ 栋房子，每栋房子都配备了一个充电站。在这座小镇上，每对房子之间至少有一条道路相互连接。在从一个房子到另一个房子的途中，最多可以进行 $C$ 次充电。每次出发时，都需要给电动车充满电（这算作一次充电）。由于 Mr. Avantgarde 并不喜欢麻烦，请帮助他计算出电动车所需的最小续航里程。 注意：每次充电后，电动车最多可以行驶与其续航里程相等的距离。

输入的第一行是一个整数 $T$，表示测试用例的数量（$0 < T < 6$）。对于每个测试用例，第一行包含三个整数 $N$、$C$ 和 $M$，分别表示房子的数量、充电次数和道路的数量（$1 < N < 101$, $0 < C < 101$）。接下来的 $M$ 行中，每行有三个整数 $u$、$v$ 和 $d$，表示房子 $u$ 和房子 $v$（编号从 $0$ 开始）之间有一条双向道路，长度为 $d$（$0 \le u, v < N$, $u \neq v$, $1 \le d \le 10^9$）。

对每组测试用例，输出电动车所需的最小续航里程。

- 测试用例数量：$0 < T < 6$ - 房子的数量：$1 < N < 101$ - 充电次数：$0 < C < 101$ - 道路距离：$1 \le d \le 10^9$ **本翻译由 AI 自动生成**