J. Toad's Travel
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

A toad is travelling in Byteland, which consists of some cities and some roads, each of which connects a pair of cities. More specifically, the map of Byteland is an undirected connected edge-weighted graph in which every edge lies on at most one simple cycle. The toad is in the city numbered by $$$1$$$ at first and wants to go through all the roads at least once.

TIME IS MONEY!

The toad must minimize the total length of the path in his travelling.

Input

The first line contains two integers $$$n,m~(2 \le n\le 10^5,n-1\leq m\leq 2n-2)$$$, indicates the number of cities and roads in Byteland.

Each of the next $$$m$$$ lines contains three integers $$$u_i, v_i, w_i~(1 \le u_i, v_i \le n, u_i \ne v_i, 0 \le w_i \le 10^5)$$$, representing a road with a length of $$$w_i$$$ connects $$$u_i$$$ and $$$v_i$$$. It's guaranteed that each pair of cities will be connected with at most one road.

Output

Output a single integer, indicating the minimum possible sum.

Example
Input
6 7
1 2 1
1 3 1
2 3 1
3 4 1
3 5 1
4 5 1
2 6 1
Output
8
Note

In the sample test, one of the best paths is $$$$$$1\rightarrow2\rightarrow6\rightarrow2\rightarrow3\rightarrow4\rightarrow5\rightarrow3\rightarrow1$$$$$$ and the total length of the path is $$$8$$$.