Micro is having a graph containing N vertices and M edges, each edge is having an associated weight. He knows for sure that the graph contains several Hamiltonian Paths (path that visits all the vertices exactly once). He challenged his friend to find out the minimum element of the array which stores the strength of all Hamiltonian Paths in the graph. Strength of a Hamiltonian Path is the sum of weight of edges in that path. But Micro himself does not know the answer to it. Help Micro in solving this problem.
Input:
First line consists of two space separated integers denoting N and M.
Each of the following M lines consists of three space separated integers X, Y and Z denoting that there is an edge between vertices X and Y having weight Z.
Output:
Print the answer in a new line.
Constraints:
1≤N≤10
1≤M≤20
1≤X,Y≤N
1≤Z≤100
There are two Hamiltonian Paths in the given graph.
1 - 2 - 3 - 4 (Strength = 10)
1 - 2 - 4 - 3 (Strength = 7)
So, array will have two elements {10, 7}, so the answer is clearly 7