In ICPCCamp, there are n cities and m directed roads between cities.
The i-th road going from the -th city to the -th city is kilometers long.
For each pair of cities (u, v), there can be more than one roads from u to v.
Bobo wants to make big news by solving the famous *Hamiltonian Path* problem.
That is, he would like to visit all the n cities one by one so that the total distance travelled is minimized.
Formally, Bobo likes to find n **distinct** integers
to minimize where w(x, y) is the length of road from the x-th city to the y-th city.

The input contains at most 30 sets. For each set:
The first line contains 2 integers n, m ().
The i-th of the following m lines contains 3 integers 
().

For each set, an integer denotes the minimum total distance.
If there exists no plan, output `-1` instead.

3 3
1 2 1
1 3 1
2 3 1

2

3 2
1 2 1
1 3 2

-1