负环

题目描述

给定一张边带权的有向图$G$，请你找出一个点数最少的环，使得环上的边权和为负数。保证图中不存在重边和自环。

输入格式

第一行两个整数$n$，$m$表示图的点数和边数。点从$1$~$n$编号。

接下来每行$3$个整数$u_{i}$，$v_{i}$，$w_{i}$，表示从$u_{i}$到$v_{i}$权值为$w_{i}$的有向边。

输出格式

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

数据范围与提示

• 对于$20\%$的数据，$n \leq 7$，$m \leq 10$；
• 对于$60\%$的数据，$n \leq 150$，$m \leq 2000$；
• 对于$100\%$的数据，$2 \leq n \leq 300$，$0 \leq m \leq n \times (n-1)$，$|w_{i}| \leq 10^{4}$。

样例

4 8
1 2 10
2 1 -3
1 3 -1
3 1 10
2 4 10
4 2 1
3 4 0
4 3 3

4