首先想到二分答案
然后我们从大往小加区间，如果之前出现了一个区间包含当前区间
那显然不合法，我们可以用并查集了维护
type node=record
x,y,mi,id:longint;
end; var q:array[..] of node;
a:array[..] of longint;
fa:array[..] of longint;
l,r,m,n,t,i,ans:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; procedure swap(var a,b:node);
var c:node;
begin
c:=a;
a:=b;
b:=c;
end; procedure sort(l,r:longint);
var i,j,x:longint;
begin
i:=l;
j:=r;
x:=q[(l+r) shr ].mi;
repeat
while x<q[i].mi do inc(i);
while q[j].mi<x do dec(j);
if not(i>j) then
begin
swap(q[i],q[j]);
inc(i);
dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; function have(l,r:longint):boolean;
var x:longint;
begin
x:=r;
while x>=l do
begin
if fa[x]= then exit(false);
x:=fa[x]-;
end;
exit(true);
end; procedure work(l,r:longint);
var x:longint;
begin
x:=r;
while x>=l do
begin
if fa[x]= then fa[x]:=l
else begin
x:=fa[x];
if x>=l then fa[x]:=l;
end;
dec(x);
end;
end; function check(m:longint):boolean;
var s,i,j,x,y,k:longint;
begin
fillchar(fa,sizeof(fa),);
s:=;
for i:= to t do
if q[i].id<=m then
begin
inc(s);
a[s]:=i;
end; i:=;
while i<s do
begin
inc(i);
j:=i+;
while (j<=s) and (q[a[i]].mi=q[a[j]].mi) do inc(j);
dec(j);
x:=;
y:=n+;
for k:=i to j do
begin
x:=max(x,q[a[k]].x);
y:=min(y,q[a[k]].y);
end;
if x>y then exit(false);
if have(x,y) then exit(false);
for k:=i to j do
work(q[a[k]].x,q[a[k]].y);
i:=j;
end;
exit(true);
end; begin
readln(n,t);
for i:= to t do
begin
readln(q[i].x,q[i].y,q[i].mi);
q[i].id:=i;
end;
sort(,t);
l:=;
r:=t-;
if check(t) then writeln()
else begin
ans:=t;
while l<=r do
begin
m:=(l+r) shr ;
if not check(m) then
begin
ans:=m;
r:=m-;
end
else l:=m+;
end;
writeln(ans);
end;
end.