题目描述

很久以前，在古老的波利尼西亚有 $n$ 个伟大的岛屿，通过魔法路径相连。岛屿编号从 $1$ 到 $n$。这些路径不仅允许旅行，还维持着魔法能量的平衡，这种能量滋养着整个世界。

然而有一天发生了灾难：女神特菲提失去了她的心脏，所有魔法路径都消失了，岛屿彼此孤立。酋长图伊迫切希望恢复秩序，召集了最优秀的萨满。魔法师们提出了一个古老的恢复仪式，根据这个仪式可以创建新的小岛——魔法节点。总共创建了 $k$ 个新岛屿。

从每个新岛屿 $n+1, n+2, \ldots, n+k$ 可以创建通往原始 $n$ 个岛屿的某些路径。更准确地说，对于每个 $i$ 从 $1$ 到 $k$，已知参数 $l_i$、$r_i$ 和 $c_i$，意味着消耗 $c_i$ 能量可以从岛屿 $n + i$ 创建一条通往岛屿 $j$ 的路径，如果 $l_i \le j \le r_i$。当然，可以从每个新岛屿引出多条路径，但每条路径都需要消耗 $c_i$ 能量。

请确定是否可以通过这些路径将所有 $n + k$ 个岛屿连接成一个统一的网络，使得从每个岛屿都可以到达任何其他岛屿。如果可能，请确定实现这一目标所需的最小能量。

如果你成功了，古老的波利尼西亚将得到拯救，昔日的魔法将让岛屿重现繁荣。但如果你失败了——岛屿将保持孤立，世界将永远陷入混乱。一切取决于你！

输入格式

第一行包含两个整数 $n$ 和 $k$——分别表示原始岛屿和新岛屿的数量（$1 \le n, k \le 2 \cdot 10^5$）。

接下来的 $k$ 行描述从新岛屿出发的可能路径：第 $i$ 行包含三个整数 $l_i$、$r_i$ 和 $c_i$——路径可能终点的边界以及每条路径的代价（$1 \le l_i \le r_i \le n$；$1 \le c_i \le 10^9$）。

输出格式

如果能够连接波利尼西亚的所有岛屿，输出所需的最小能量。如果不可能，输出 $-1$。

4 3
1 3 2
1 2 4
2 4 5

20

6 2
4 6 7
1 2 7

-1

100000 4
1 100000 10
1 100000 76
1 100000 12
1 100000 12

1000100