可能有人像我一样认为无脑使用技能是不劣的，并且最短路上每条边至多走过一次。所以直接输出第 $k$ 层的 $dis_n$，得到 80pts。

原因：即使全程使用减半技能，也可能在不用完 $k$ 次能力的情况下到达终点。

输入：

2 1 2
1 2 2

输出：

1