题目要求我们找出一个包含点数最少的负环，我们考虑最终答案是什么样子的。

手模几组小数据，画画图，发现最终答案一定是个简单环（包含n个点n条边），那么我们可以通过边数确定点数。

我们设 $f_{k,i,j}$ 表示从 $i$ 走到 $j$ 走 $k$ 步的最小值，转移和昨天T4类似。

我们注意到一个结论，对于一个点 $i$ ，我们找到最小的 $l$ 满足 $f_{l,i,i}$ 小于 $0$ ，那么 $l$ 就是以 $i$ 为起点的负环的最小长度。

可以利用反证法证明，如果说 $l$ 不是最小长度的话，那么一定存在一个 $l'$ 满足 $f_{l',i,i}$ 小于0，与前提矛盾了，所以不成立。

而且这个环一定是个简单环，也可以用反证法证明，假设不是简单环，那么这个复杂环里面一定存在一个 $i$ 开头的简单负环，说明也存在一个 $l'$ 满足 $f_{l',i,i}$ 小于0，与前提矛盾，不成立。

最后我们可以利用类似倍增跳 $lca$ 的方法维护。

注意一些实现的小细节，为了保证 $f$ 的单调性（方便倍增），我们要把 $dis_{i,i}$ 赋值为0而不是极大值。

#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define ll long long
#define wswlovewbn 5201314
#define INF (1e9)
using namespace std;
const int N=301;
int n,m,S,T,u,v,k,w=0;
struct Martix{
	int p[N][N];
}M[9];
int getmin(int x,int y){
	return x>y?y:x;
}
Martix operator*(const Martix A,const Martix B){
	Martix C;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			C.p[i][j]=INF;
			for(int k=1;k<=n;k++){
				C.p[i][j]=getmin(C.p[i][j],A.p[i][k]+B.p[k][j]);
			}
		}
	}return C;
}
Martix res,nw;
bool check(Martix x){
	for(int i=1;i<=n;i++){
		if(x.p[i][i]<0)return 1;
	}return 0;
}
int ans;
int main(){
//	freopen("ex.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j)M[0].p[i][j]=res.p[i][j]=INF;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		M[0].p[u][v]=w;
	}
	for(int i=1;i<=8;i++)M[i]=M[i-1]*M[i-1];
	for(int i=8;i>=0;i--){
		nw=res*M[i];
		if(!check(nw)){
			if(i==8){
				puts("0");return 0;
			}
			res=nw,ans+=(1<<i);
		}
	}
	printf("%d\n",ans+1);
	return 0;
}