HOME_W的签到题O(∩_∩)O

在一维数轴上给出m个线段，每个线段都都有l,r,w三个数据代表这个线段的左右端点和这个区间权值。 从中取出若干个不相交的线段(区间端点可以共用)，在覆盖满[1,n]的情况下，取出的线段中【权重的最大值】最小能为多少？

这里对覆盖满[1,n]做一下具体说明，所谓覆盖满就是，要每个位置有线段盖住，不能留空。

比如[1 2] [3 4] 在2,3之间留了个空，是非法的，不算覆盖满[1,4]

多组数据。

每组数据第一行包含两个整数n,m。

接下来有m行，每行包含3个整数l_i,r_i,w_i,分别代表线段的左右端点和权重

1<=n<=100000

1<=m<=min(200000,n(n-1)/2)

0<=wi<2³⁰

1<=l_i<r_i<=n

Σ(n+m)<=2,000,000

若无解输出"invalid data"。否则输出题面描述的所描述最大权值的最小值。

6 6
2 4 8
3 4 6
4 5 3
5 6 8
1 6 9
2 5 3
6 6
2 3 6
3 5 2
4 6 4
5 6 2
1 3 7
2 4 4
3 1
1 2 1

9
7
invalid data