题目描述

在忘记考虑负环之后，黎瑟的算法又出错了。对于边带权的有向图 $G = (V, E)$，请找出一个点数最小的环，使得环上的边权和为负数。保证图中不包含重边和自环。

输入格式

第一行两个整数 $n,m$，表示图的点数和边数。
接下来的 $m$ 行，每行三个整数 $u_i,v_i,w_i$，表示有一条从 $u_i$ 到 $v_i$，权值为 $w_i$ 的有向边。

输出格式

仅一行一个整数，表示点数最小的环上的点数，若图中不存在负环输出 0。

3 6
1 2 -2
2 1 1
2 3 -10
3 2 10
3 1 -10
1 3 10

2

数据规模与约定

对于 $100\%$ 的数据，$2 \le n \le 300$，$0 \le m \le n\times (n-1)$，$1 \le u_i,v_i\le n$，$|w_i| \le 10^4$。