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.

dmFyCiAgbSxuLGksayx0OmludGVnZXI7CiAgYSxiLGM6YXJyYXlbMS4uMTAwLDEuLjJdIG9mIGludGVnZXI7CmJlZ2luCiAgcmVhZGxuKG0sbik7CiAgZm9yIGk6PTEgdG8gbiBkbyBiZWdpbgogICAgcmVhZGxuKGFbaSwxXSxiW2ksMV0sY1tpLDFdKTsKICAgIGFbaSwyXTo9MTsKICAgIGJbaSwyXTo9MDsKICAgIGNbaSwyXTo9Y1tpLDFdOwogIGVuZDsKICBrOj0wO3Q6PTA7CiAgcmVwZWF0CiAgICB0Oj10KzE7CiAgICBmb3IgaTo9MSB0byBuIGRvIGJlZ2luCiAgICAgIGlmIGNbaSwxXT1jW2ksMl0gdGhlbiBiZWdpbgogICAgICAgIGlmIGFbaSwxXT1hW2ksMl0gdGhlbiBiZWdpbgogICAgICAgICAgazo9aysxOwogICAgICAgICAgYVtpLDJdOj0xOwogICAgICAgICAgaW5jKGJbaSwyXSk7CiAgICAgICAgICBpZiBiW2ksMV09YltpLDJdIHRoZW4gYmVnaW4KICAgICAgICAgICAgYltpLDJdOj0wOwogICAgICAgICAgICBjW2ksMl06PTA7CiAgICAgICAgICBlbmQ7CiAgICAgICBlbmQgZWxzZSBpbmMoYVtpLDJdKTsKICAgICAgZW5kIGVsc2UgaW5jKGNbaSwyXSk7CiAgICBlbmQ7CiAgdW50aWwgaz49bTsKICB3cml0ZWxuKHQpOwplbmQu

MTAgMwoxIDIgMwozIDEwIDMKMiA0IDM=

10 3
1 2 3
3 10 3
2 4 3