9576: 毕业旅行

转眼间，克利切洛夫斯基已经是一名大四的学生了。为了给自己的青春画上一个完美的句号，他决定和好朋友们一起进行一次毕业旅行。 毕业旅行的起点是$1$号城市，终点是$N$号城市。他们将会乘坐火车在不同城市之间穿梭，每次乘车将会从一个城市到达另一个城市，并花费不同的金额。学过算法的克利切洛夫斯基同学很快就想到，如果要让花费的总金额最小，这不就是最短路吗？于是他很快使用最短路算法计算出了最小花费。但他的ICPC队友提醒他，他已经报名了刘老师的春季联赛，就算快要毕业了也不要浪费任何一次训练机会。所以他同样希望能够经过不超过$X$个城市，这样才能赶上参加春季联赛。克利切洛夫斯基想请你帮他计算出在这个前提下的最小花费。 毕业旅行共有$N$个可能经过的城市，其中起点$1$和终点$N$一定会经过。共有$M$条不同的火车线路，第$i$条线路的起点是$a_i$，终点是$b_i$，花费的金额是$c_i$。 可能存在重边或者自环。题目保证一定有合法的解。

本题单个测试点内包含多组测试数据。 输入第一行一个正整数 $T$ $(1 \leq T \leq 10)$，表示数据组数。 每组数据： - 第一行三个整数 $N$ $(1 \leq N \leq 10^5)$，$M$ $(1 \leq M \leq 2 \times 10^5)$ 和 $X$ $(2 \leq X < N)$，分别表示城市的数量、火车线路的数量和期望最多经过多少个城市 - 接下来$M$行，每行3个整数$a_i$,$b_i$,$c_i$，表示第$i$条线路的起点、终点和花费金额$(1 \leq a_i,b_i \leq N$，$1 \leq c_i \leq 10^6)$ 保证所有数据$M$的总和不超过$10^6$。

每组数据仅一行一个整数，表示经过最多$X$个城市的旅行方案中，最少需要花费多少钱。起点和终点同样包括在内，且不能重复经过同一个城市。

- $1 \leq T \leq 10$ - $1 \leq N \leq 10^5$ - $1 \leq M \leq 2 \times 10^5$ - $2 \leq X < N$ - $1 \leq c_i \leq 10^6$ - 所有测试数据$M$的总和不超过$10^6$ - 保证每组数据都有解