最小点数负环

题目描述

给定一张 $n$ 个顶点 $m$ 条边的带权有向简单图，顶点编号从 $1$ 到 $n$，请找出一个顶点数最小的环，使得环上的边权和为负数。

输入格式

第一行两个整数 $n, m$，表示顶点数和边数。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示 $u$ 号点到 $v$ 号点有一条边权为 $w$ 的边。

输出格式

输出一行一个整数表示顶点数最小的负环上的顶点数，如果不存在负环输出 -1。

样例输入

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

样例输出

2

数据范围

对于 $100\%$ 的数据，保证 $1\leq n\leq 300, 0\leq m\leq n(n-1), 1\leq u, v\leq n, -10^4\leq w\leq 10^4$。