Migrated from Lutece 3166 你好世界

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

鸡煲对尖塔发出了挑战。

尖塔一共有 $n$ 层，现在鸡煲位于第 $1$ 层，他想到达塔顶的第 $n$ 层。但是在观者爬完塔后，尖塔的所有路径都被破坏了。

为了能够顺利爬塔，鸡煲将要进行 $m$ 次操作，每次操作指定区间 $[l_i,r_i]$，在所有满足 $l_i\leq u,v\leq r_i$ 的点对 $(u,v)$ 之间添加一条长度为 $c_i$ 的无向边。

在进行完所有操作后，鸡煲想知道到达塔顶的最短路，由于鸡煲忙着roll爽种，现在请你帮助他解决这个问题。

Input

第一行两个正整数 $n,m(2\leq n\leq3×10^5,1\leq m \leq 3×10^5)$。

接下来 $m$ 行，每行三个正整数$l_i,r_i,c_i(1\leq l_i<r_i\leq n,1\leq c_i\leq10^9)$。

Output

输出一个整数,表示 $1$ 到 $n$ 间的最短路，如果无法到达点 $n$，输出 $-1$。

Samples

4 3
1 3 2
2 4 3
1 4 6

5

Resources

2024 UESTC ICPC Training for Graph