410438: GYM104021 J Toad's Travel

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.

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 a single integer, indicating the minimum possible sum.

6 7
1 2 1
1 3 1
2 3 1
3 4 1
3 5 1
4 5 1
2 6 1

8

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$$$.