← 返回题目列表

AtCoder · nikkei2019_2_qual_d

D. 直线上的最短路径

中文机器翻译题面 查看原题

分数: 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