U651695 简单最短路
题目背景
JKQ 杯 2026/05/11 T6（CF1800）。
题目描述
解决了漂流瓶上的排列问题使你心情大好，但你现在需要与魔女 C 会面，你现在在基地 $1$，魔女 C 在基地 $n$，基地之间有 $m$ 条相互连接的道路，形成一个无向图，不使用魔力通过需要消耗 $w_i$ 单位时间，或使用魔力瞬间移动不消耗时间，由于协会限制，你们最多使用 $k$ 次魔力，你需要对于所有使用魔力次数的情况求出最小时间，依旧按使用次数顺序给出。数据多测，且保证存在 $1$ 到 $n$ 的路径经过的点数不大于 $100$。
输入格式
输入第 $1$ 行只有一个正整数 $T$，表示数据组数。
每组输入第 $1$ 行有 $3$ 个整数 $n,m,k$，基地个数，道路数和魔力限制。
之后 $m$ 行每行 $3$ 个整数 $u,v,w$，一条道路的起点，终点及消耗时间。
输出格式
输出有 $T$ 行，第 $i$ 行 $k_i + 1$ 个数，对应表示每组的使用魔力多少的最小时间，不带前后缀 $0$ 完整输出。
说明/提示
### 【样例解释 #1】:
图如下（边 $(3, 4, 0)$ 实际为 $(3, 4, 1)$）：
不使用魔力最小时间路径为：$1 \rightarrow 2 \rightarrow (touched\ at\ time=4.5) \leftarrow 3 \leftarrow 4 \leftarrow 5$，使用 $1$ 次只需走 $(1, 5, 10)$ 一条路。
| 测试点 | $T$ | $n$ | $m$|
| :---: | :---: |:---:|:---:|
|$1 \sim 2$|$\le 10$|$\le 20$| $\le 20$ |
|$3 \sim 9$|$\le 100$|$\le 100$| $\le 100$ |
|$10 \sim 15$|$\le 10 ^ 3$|$\le 20$| $\le 10 ^ 3$ |
|$16 \sim 20$|$\le 10 ^ 3$|$\le\ 10 ^ 3$| $\le 10 ^ 3$ |
对于 $100\%$ 的数据，$1 \le T \le 10 ^ 3,1 \le n,m \le 10 ^ 3,1 \le \sum n,\sum m \le 10 ^ 4,0 \le k \le m,1 \le w \le 10 ^ 9$。