#4773. 负环

题目描述

在忘记考虑负环之后，黎瑟的算法又出错了。对于边带权的有向图 G = (V, E)，请找出一个点数最小的环，使得

环上的边权和为负数。保证图中不包含重边和自环。

输入格式

第1两个整数n, m,表示图的点数和边数。

接下来的m行，每<=三个整数ui, vi, wi，表<=有一条从ui到vi，权值为wi的有向边。

2 <= n <= 300

0 <= m <= n(n <= 1)

1 <= ui, vi <= n

|wi| <= 10^4

输出格式

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

样例

样例输入

3 6  

1 2 -2  

2 1 1  

2 3 -10  

3 2 10  

3 1 -10  

1 3 10  

样例输出

2

数据范围与提示