题目描述

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

输入

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

输出

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

输入样例

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

提示

【数据规模】 对于20%的数据：$n≤7，m≤10$； 对于60%的数据：$n≤150，m≤2000$； 对于100%的数据：$2≤n≤300，0≤m≤n×(n-1),|w_i|≤10^4$。

图方向说明

按输入小节的有向边定义处理。描述小节误写了无向；公开样例同时给出1→2权10和2→1权-3，并声明无重边，这也排除了无向解释。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。