const oo=;

 var d:array[..,..,..]of longint;

     g,f:array[..,..]of longint;

     n,m,i,j,k,t,ans,x,y,z:longint;

     flag:boolean;

 function min(x,y:longint):longint;

 begin

  if x<y then exit(x);

  exit(y);

 end;

 begin

  assign(input,'cycle.in'); reset(input);

  assign(output,'cycle.out'); rewrite(output);

  readln(n,m);

  for i:= to n do

   for j:= to n do

    if i<>j then d[,i,j]:=oo;

  for i:= to m do

  begin

   readln(x,y,z);

   d[,x,y]:=min(d[,x,y],z);

  end;

  for t:= to  do

  begin

   for i:= to n do

    for j:= to n do

     if i<>j then d[t,i,j]:=oo;

   for i:= to n do

    for j:= to n do

     for k:= to n do d[t,i,k]:=min(d[t,i,k],d[t-,i,j]+d[t-,j,k]);

  end;

  for i:= to n do

   for j:= to n do

    if i<>j then f[i,j]:=oo;

  for t:= downto  do

  begin

   for i:= to n do

    for j:= to n do g[i,j]:=f[i,j];

   for i:= to n do

    for j:= to n do

     for k:= to n do f[i,k]:=min(f[i,k],g[i,j]+d[t,j,k]);

   flag:=false;

   for i:= to n do

    if f[i,i]< then begin flag:=true; break; end;

   if flag then

   begin

    for i:= to n do

     for j:= to n do f[i,j]:=g[i,j];

   end

    else ans:=ans+(<<t);

  end;

  inc(ans);

  if ans>n then writeln()

   else writeln(ans);

  close(input);

  close(output);

 end.