Negative Weight Cycle solved by 378

Problem

The task is to use Bellman-Ford algorithm to check whether a given graph contains a cycle of negative weight.

Given: A positive integer $k \le 20$ and $k$ simple directed graphs with integer edge weights from $-10^{3}$ to $10^3$ and $n \le 10^3$ vertices in the edge list format.

Return: For each graph, output "1" if it contains a negative weight cycle and "-1" otherwise.

Sample Dataset

2

4 5
1 4 4
4 2 3
2 3 1
3 1 6
2 1 -7

3 4
1 2 -8
2 3 20
3 1 -1
3 2 -30

Sample Output

-1 1