分数: 600 点
问题陈述
我们有 N 点编号 1 to N 按此顺序排列成行。
Takahashi 决定制作一个无向图,使用这些点作为顶点。 一开始,图没有边。高桥会做 M 操作在此图中添加边。 的 i第次操作如下:
- 运算使用整数 L_i 和 R_i 之间 1 和 N (含),和一个正整数 C_i。对于每对整数 (s, t) 这样 L_i \leq s < t \leq R_i,添加一条边长度 C_i 顶点之间 s 和顶点 t.
整数 L_1, ..., L_M, R_1, ..., R_M, C_1, ..., C_M 全部作为输入给出。
Takahashi想要解决最终获得的图中的最短路径问题。求从顶点出发的最短路径的长度 1 到顶点 最终图表中的 N 。
约束
- 2 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq L_i < R_i \leq N
- 1 \leq C_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N M L_1 R_1 C_1 : L_M R_M C_M
输出
打印从顶点开始的最短路径的长度
最终图表中的 1 到顶点
最终图表中的 N 。
如果没有最短路径,则打印 -1 。
示例输入 1
4 3 1 3 2 2 4 3 1 4 6
示例输出 1
5
我们有一条长度的边 2 顶点之间 1 和顶点 2,以及长度的边 3 顶点之间 2 和顶点 4,所以有一条长度的路径 5 顶点之间 1 和顶点 4.
示例输入 2
4 2 1 2 1 3 4 2
示例输出 2
-1
示例输入 3
10 7 1 5 18 3 4 8 1 3 5 4 7 10 5 9 8 6 10 5 8 10 3
示例输出 3
28