Exercise Route

A city has V villages and E one-way roads. The villages are numbered from 1 to V.

You want to choose a route for exercise by following the roads. Since the route should end at the village where it started, it must form a cycle using one or more roads. Among all possible cycles, find the minimum possible sum of road lengths.

Traveling from one village to another and then back along an oppositely directed road also counts as a cycle.

The first line contains V and E separated by a space. (2 <= V <= 400, 0 <= E <= V(V-1))

Each of the next E lines contains three integers a, b, and c. This means there is a one-way road of length c from village a to village b. Each distance is a positive integer not greater than 10,000, and the same ordered pair (a, b) is not given more than once.

Print the minimum sum of road lengths in a cycle. If no cycle exists, print -1.