Shortest Cycle Through a Given Edge solved by 416

Problem

Given: A positive integer $k \le 20$ and $k$ simple directed graphs with positive integer edge weights and at most $10^3$ vertices in the edge list format.

Return: For each graph, output the length of a shortest cycle going through the first specified edge if there is a cycle and "-1" otherwise.

Sample Dataset

2

4 5
2 4 2
3 2 1
1 4 3
2 1 10
1 3 4

4 5
3 2 1
2 4 2
4 1 3
2 1 10
1 3 4

Sample Output

-1 10