分数: 400 分
问题陈述
高桥使用铁路网络进行通勤,其中包括 N 连接的站 M 行。车站编号从 1 to N。线 i 双向连接站 U_i 和车站 V_i,票价为 C_i 日元。
高桥每天需要从车站通勤 1, 离他家最近的车站, 到车站 N,距离他工作地点最近的车站。由于高桥的交通预算仅为 K 日元,他必须找到一条总票价最多为 K 日元。
这里,一个 路线 指的是从车站出发的路径 1 及后续线路依次到达车站 N。允许多次访问同一车站或多次使用同一条线路。一条路线的总票价是该路线所使用的所有线路的票价之和。如果多次使用同一条线路,则每次使用均需付费。
如果存在从车站出发的路线 1 到车站 N 总票价最多为 K 日元,输出所有此类航线中最低的总票价。如果不存在这样的路由,则输出 -1.
约束
- 2 \leq N \leq 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 1 \leq U_i, V_i \leq N
- U_i \neq V_i
- 可能有多条线路连接同一对车站
- 1 \leq C_i \leq 10^9
- 所有输入值均为整数
输入
N M K U_1 V_1 C_1 U_2 V_2 C_2 \vdots U_M V_M C_M
- 第一行包含 N 代表站数, M 代表行数,以及 K 代表高桥的交通预算,以空格分隔。
- 从第 2 行到 (M + 1)第行,有关的信息 给出了 M 行。
- 的 (1 + i)第 行包含两个车站 U_i, V_i 通过线路连接 i 和票价 C_i,以空格分隔。
输出
如果存在从车站出发的路线 1 到车站 N 总票价最多为 K 日元,输出一行中最低的总票价。如果不存在这样的路由,则输出 -1 一行。
示例输入 1
4 4 10 1 2 3 2 4 5 1 3 7 3 4 2
示例输出 1
8
示例输入 2
3 2 5 1 2 3 2 3 4
示例输出 2
-1
示例输入 3
6 8 15 1 2 4 1 3 2 2 4 5 3 4 3 2 5 7 4 5 1 4 6 8 5 6 2
示例输出 3
8