Mohit is a delivery executive of the company called Swiggy. Swiggy recently started batching orders, so Mohit needs to carry out orders from restaurants.
There are junctions with its own restaurant in each and bidirectional roads. It's guaranteed that the graph is connected. Mohit is currently located at a collection booth which is denoted as a junction in the graph. He needs to visit all restaurants in some order according to the given rules and come back to the collection booth.
Let's say Mohit is currently at junction . He can go to the neighboring junction if one of the following statements is true:
- There is a road connecting and , and Mohit haven't visited junction before.
- Mohit arrived junction from junction . It means he just goes back to where he came from.
Your job is to calculate the minimum distance covered by Mohit. Note that Mohit has to finish his trip at the junction at the end.
Input Format
First line contains two integers and denoting the number of junctions and the number of roads, respectively.
Next lines contain , , and denoting the road between and with distance . It's guaranteed that and there are no two roads connecting the same pair of junctions.
Constraints
- and
Output Format
Output the answer.
Sample Input 0
2 3
0 1 1
2 0 3
1 2 2
Sample Output 0
6
Explanation 0
First, Mohit goes to the restaurant, then to the restaurant. He then goes back to the collection booth by first going back to restaurant, then to collection booth. So the answer would be .