You are given an undirected weighted graph with N nodes and M edges. The nodes are marked with the numbers 1 to N. Every edge connects to different nodes and has positive weights. Find the cycle with the lowest weight that contains the nodes 1 and N and whose path goes through every node at most once. A cycle is a path that goes from node 1 to node N and then goes back to 1.

INPUT:
The data should be read from the standard input. The first line contains the integers N and M (2 <= N <= 1000, 1 <= M <= 10000), which represent the number of nodes and edges in the graph. Each of the next M lines contain the three integers X , Y and W separated by a single space (1 <= X , Y <= N, 1 <= W <= 100000), which represent an edge with weight W that connects X and Y.

OUTPUT:
In one line in the standard output, write one integer representing the weight of the cycle with the lowest weight from 1 to N. It is guaranteed that every given input will have at least one cycle.

Input:


Output:

Explanation: the Cycle 1 -> 2 -> 4 -> 3 -> 1 is the solution, with the weight 1 + 2 + 1 + 2 = 6.