分数: 400 分
问题陈述
高桥是一名送货员。今天,他必须以最快的速度前往送货目的地,递送包裹。
送货区域包含 N 位置,编号自 1 to N。高桥从配送中心所在地出发 1 并旨在到达送货目的地所在位置 N.
有 M 地点之间的单向道路。的 i第路(1 \leq i \leq M) 是一条从位置出发的单向道路 U_i 到位置 V_i,并且需要 C_i 是时候沿着这条路旅行了。同一对位置可能有多条道路 (U_i, V_i).
高桥可能会多次经过同一位置。求从配送中心(位置 1)到交货目的地(位置 N).
保证位置 N 可从以下位置到达 1.
约束
- 2 \leq N \leq 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq U_i \leq N
- 1 \leq V_i \leq N
- U_i \neq V_i
- 1 \leq C_i \leq 10^9
- 同一对 (U_i, V_i) 可能会多次给出
- 位置 N 可从以下位置到达 1
- 所有输入值均为整数
输入
N M U_1 V_1 C_1 U_2 V_2 C_2 \vdots U_M V_M C_M
- 第一行包含位置数 N 和道路数量 M,用空格分隔。
- 以下 M 每行描述一条路: i这些行中的第 (1 \leq i \leq M) 包含起点 U_i,终点 V_i,以及行程时间 C_i 的 i第条路,以空格分隔。这条路是从该地点出发的单向道路 U_i 到位置 V_i.
输出
打印从该地点出发所需的最短时间 1 到位置 N 作为单行上的整数。
示例输入 1
4 5 1 2 3 1 3 5 2 3 1 2 4 10 3 4 2
示例输出 1
6
示例输入 2
6 9 1 2 7 1 3 9 1 4 14 2 3 10 2 5 15 3 4 2 3 5 11 4 5 9 5 6 6
示例输出 2
26
示例输入 3
10 15 1 2 1000000000 1 3 500000000 2 4 300000000 3 4 200000000 3 5 400000000 4 6 100000000 5 6 150000000 5 7 250000000 6 7 50000000 6 8 200000000 7 8 100000000 7 9 300000000 8 9 150000000 8 10 400000000 9 10 100000000
示例输出 3
1200000000