最小生成树(tree)

题目描述

江老师有一张无向图, 现在他想考考你会不会求最小生成树。

但传统的最小生成树题目中, 图往往十分的稀疏, 这令江老师十分不满。

于是江老师定义了一种全新的连边方式, 对于一次连边操作 $(l,r,w)$, 其表示的意义为

• 对于所有满足 $l\le u < v\le r$ 的点对 $(u,v)$, 在 $u,v$ 间连一条边权为 $w$ 的边

现在江老师请你求出这张图最小生成树的边权和。

输入格式​

第一行两个整数 $n,m$, 表示图中有 $n$ 个点, 共有 $m$ 次连边操作。

第 $i+1$ 行有三个整数 $l_i,r_i,w_i$, 表示第 $i$ 次连边操作的参数 $(l,r,w)$。

输出格式

输出一行, 包含一个整数，即该图最小生成树的边权和, 若该图不连通则输出 $-1$。

样例

输入1

3 1
1 2 3

输出1

-1

输入2

3 2
1 3 4
1 2 3

输出2

7

样例3 见样例文件夹

数据范围与提示

对于全部数据, 满足 $1\le l_i