Code:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 303
#define inf 1000000000
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
namespace IO
{
char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )
int rd() { int x = 0, f = 1;char c = nc();while (c < 48) {if (c == '-')f = -1;c = nc();}while (c > 47) {x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();}return x * f;}
};
int n,m,dis[N][N][10],tmp[2][N][N];
inline void getmin(int &a,int b) { if(b<a)a=b; }
inline int check()
{
int i;
for(i=1;i<=n;++i) if(tmp[1][i][i]<0) return 1;
return 0;
}
int main()
{
int i,j,k,l,ans=inf;
// setIO("input");
n=IO::rd(),m=IO::rd();
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
for(k=0;k<10;++k) dis[i][j][k]=inf;
}
for(i=1;i<=n;++i) for(k=0;k<10;++k) dis[i][i][k]=0;
for(i=1;i<=m;++i)
{
int a=IO::rd(),b=IO::rd(),c=IO::rd();
getmin(dis[a][b][0], c);
}
for(l=1;l<10;++l)
{
for(k=1;k<=n;++k)
for(i=1;i<=n;++i)
{
if(dis[i][k][l-1]==inf) continue;
for(j=1;j<=n;++j)
{
if(dis[i][k][l-1]<inf && dis[k][j][l-1]<inf)
getmin(dis[i][j][l],dis[i][k][l-1]+dis[k][j][l-1]);
}
}
}
for(i=1;i<=n;++i) for(j=1;j<=n;++j) tmp[0][i][j]=inf;
for(i=1;i<=n;++i) tmp[0][i][i]=0;
int now=0;
for(l=9;l>=0;--l)
{
for(i=1;i<=n;++i) for(j=1;j<=n;++j) tmp[1][i][j]=tmp[0][i][j];
for(k=1;k<=n;++k)
for(i=1;i<=n;++i)
{
if(tmp[0][i][k]==inf) continue;
for(j=1;j<=n;++j)
getmin(tmp[1][i][j], tmp[0][i][k]+dis[k][j][l]);
}
if(check()) getmin(ans,now|(1<<l));
else
{
now|=(1<<l);
for(i=1;i<=n;++i) for(j=1;j<=n;++j) tmp[0][i][j]=tmp[1][i][j];
}
}
printf("%d\n",ans==inf?0:ans);
return 0;
}