【样例1解释】
依次经过 1 号道路、2 号道路、3 号道路，并在经过 1、2 号道路前使用魔法。
【样例2解释】
依次经过 1 号道路、2 号道路、1 号道路，并在两次经过 1 号道路前都使用魔法。
【数据范围与提示】
对于所有测试点和样例满足：
$1 \le n \le 100,1 \le m \le 2500,0 \le K \le 10^6,1 \le u_i,v_i \le n,1 \le t_i \le 10^9$
数据保证图中无自环，无重边，至少存在一条从 $1$ 号城市到达 $n$ 号城市的路径。
每个测试点的具体限制见下表。
|
测试点编号
|
$n \le$
|
$m \le$
|
$K \le$
|
特殊限制
|
|
$1 \sim 2$
|
$5$
|
$20$
|
$0$
|
无
|
|
$3 \sim 4$
|
$10$
|
$20$
|
$50$
|
无
|
|
$5 \sim 6$
|
$10$
|
$20$
|
$0$
|
无
|
|
$7 \sim 8$
|
$20$
|
$200$
|
$50$
|
图中无环
|
|
$9 \sim 10$
|
$20$
|
$200$
|
$0$
|
无
|
|
$11 \sim 12$
|
$100$
|
$200$
|
$50$
|
图中无环
|
|
$13 \sim 14$
|
$100$
|
$200$
|
$50$
|
无
|
|
$15 \sim 18$
|
$100$
|
$2500$
|
$1000$
|
无
|
|
$19 \sim 20$
|
$100$
|
$2500$
|
$10^6$
|
无
|