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.