Description

大G学长化身恶龙，绑走了小K学长未来的女朋友——王国的公主。国王非常着急，向身为时间第一勇士的小K学长寻求帮助，并承诺若救回公主，就将公主许配给他！！！

这个国家共有$n$个城市，编号从$1$到$n$,按此顺序排成一行。大G学长占据了第 $n$ 个城市作为自己的老巢，而小K学长需要从作为王都的 $1$ 号城市出发。大G学长并不希望小K学长能那么顺利的来到他的面前，救走王国的公主，所以他摧毁了这 $n$ 个城市沿途的道路。

小K学长为了能早早的救回女朋友——公主，他向伟大的天神大S学长许愿，但是大S学长并不想这个有趣的事情那么早的结束。所以，他按照自己的奇思妙想进行了$m$次操作。第$i$次操作如下:该操作使用 1 和 $n$(含)之间的整数 $l_i$ 和 $r_i$，以及正整数 $c_i$。对于每对整数 $( s, t )$ 且 $l_i \leq s < t \leq r_i$；在城市 $s$ 和城市 $t$ 之前建了一条长度为 $c_i$ 的道路。

因为小K学长需要去面对最后的恶龙，所以他需要保留尽量多的体力，也就意味着他从王都前往恶龙的老巢需要走最短的路径。但是小K学长被大S学长的神奇操作整的有些混乱，所以他向聪明的你求助，希望你计算出来从王都到恶龙老巢的最短路径长度。

因为大S学长在那天喝的有点多，思维有些混乱，所以并不能完全保障有一条路可以从王都到达恶龙的老巢。

Format

Input

第一行输入一个正整数$n(2 \leq n \leq10^5)$和一个正整数$m(1 \leq m \leq10^5)$,表示有$n$个城市和$m$次操作。

接下来的$m$行, 每行输入三个正整数：$l_i,r_i,c_i$。其中$1\leq l_i < r_i \leq n, 1 \leq c_i \leq 10^9$。

Output

打印最终从王都到恶龙老巢的最短路径。如果没有最短路径，则打印-1。

Samples

4 3
1 3 2
2 4 3
1 4 6

5

4 2
1 2 1
3 4 2

-1

10 7
1 5 18
3 4 8
1 3 5
4 7 10
5 9 8
6 10 5
8 10 3

28

Hint