var
  m,n,i,k,t:integer;
  a,b,c:array[1..100,1..2] of integer;
begin
  readln(m,n);
  for i:=1 to n do begin
    readln(a[i,1],b[i,1],c[i,1]);
    a[i,2]:=1;
    b[i,2]:=0;
    c[i,2]:=c[i,1];
  end;
  k:=0;t:=0;
  repeat
    t:=t+1;
    for i:=1 to n do begin
      if c[i,1]=c[i,2] then begin
        if a[i,1]=a[i,2] then begin
          k:=k+1;
          a[i,2]:=1;
          inc(b[i,2]);
          if b[i,1]=b[i,2] then begin
            b[i,2]:=0;
            c[i,2]:=0;
          end;
       end else inc(a[i,2]);
      end else inc(c[i,2]);
    end;
  until k>=m;
  writeln(t);
end.