Limits 500ms, 512 MB

December 14, 1975

Hogwarts School of Witchcraft and Wizardry

It’s been a long long day. The Marauders have been caught in the act again and put into detention.

To avoid further punishments, one of them, James Potter, came up with a sly idea. He wanted to make a map of Hogwarts that would include all the hiding places, showing the position of each teacher as well. The others liked the idea and they started working on it immediately.

They initially categorized the whole castle into a set of nodes, nn. To develop the map, they needed information about the set of corridors, mm. One corridor is defined as an edge that connects two nodes.

They found out an interesting characteristic during the development of the map. The whole Hogwarts castle was connected, that means it was always possible to go from one place to another. Not very surprising, eh? But. There was only one path from one place to another.

Due to this crucial constraint, they had to use each and every corridor. So, in order to gather the required information, they decided to start their journey from a particular node, visit all the nodes in the castle and return to the starting node in the end.

Sounds pretty easy, right? That’s where Meena comes in. For this task, you don’t need to know how Meena got there. The Marauders need to bribe Meena to find out more about the corridors. In other words, they need to pay CiC_i Lifebuoy Soaps in order to learn about the corridor from AiA_i to BiB_i. The misery doesn’t end there. For each corridor that goes from place AiA_i to place BiB_i the Marauders need to pay CiC_i Lifebuoy Soaps to go from AiA_i to BiB_i, and also when they go from BiB_i to AiA_i.

Okay, enough description for a day. Here’s the problem: You are given the map of Hogwarts. The nodes are numbered from 1 to n. The Marauders will start their journey from a node. You have to find out the minimum amount of Lifebuoy Soaps the Marauders need to make in order to gather information about all the corridors and come back to the starting node.

Input

In a single line, you will be given nn and mm (0n,m1000000 \le n, m \le 100000), the number of nodes and the number of corridors respectively.

In the next mm lines, you will be given three integers, AiA_i, BiB_i and CiC_i. This means that it is possible to go from AiA_i to BiB_i with CiC_i (1Ai,Bi,Ci1000001 \le A_i, B_i, C_i \le 100000) Lifebuoy soaps. It is also possible to go from BiB_i to AiA_i with CiC_i Lifebouy Soaps.

Output

In a single line, you have to print the minimum number of Lifebuoy Soaps they would need to pay.

Sample

InputOutput
3 2
1 2 1
2 3 2
6

Submit

Login to submit.

Statistics

91% Solution Ratio
msatatm1322Earliest, Aug '17
MR.Jukerburg11Fastest, 0.0s
msatatm1322Lightest, 131 kB
mdvirusShortest, 100B
Toph uses cookies. By continuing you agree to our Cookie Policy.