Minimum-Vertex Negative Cycle

Problem Description

Given a directed weighted simple graph with $n$ vertices and $m$ edges, with vertices numbered from $1$ to $n$, find a cycle with the smallest number of vertices such that the sum of edge weights on the cycle is negative.

Input Format

The first line contains two integers $n, m$, the number of vertices and edges.

The next $m$ lines each contain three integers $u, v, w$, meaning there is a directed edge of weight $w$ from vertex $u$ to vertex $v$.

Output Format

Output one line with an integer: the number of vertices on the smallest negative cycle. If no negative cycle exists, output -1.

Sample Input

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

Sample Output

2

Constraints

For $100\%$ of the data: $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$.