Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

*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, **n**. To develop the map, they needed information about the set of corridors,**m**. 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 build **Ci** Shasthoshommoto Paykhanas in order to learn about the corridor from **Ai** to **Bi**. The misery doesn’t end there. For each corridor that goes from place **Ai** to place **Bi** the Marauders need to build **Ci** Paykhanas to go from **Ai** to **Bi**, and also when they go from **Bi** to **Ai**.

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 Shasthoshommoto Paykhanas the Marauders need to make in order to gather information about all the corridors and come back to the starting node.

In a single line, you will be given **n** and **m**, the number of nodes and the number of corridors respectively.**0 <= n, m <= 100000**

In the next **m** lines, you will be given three integers, **Ai**, **Bi** and **Ci**. This means that it is possible to go from **Ai** to **Bi** with **Ci** Shasthoshommoto Paykhanas. It is also possible to go from **Bi** to **Ai** with **Ci** Shasthoshommoto Paykhanas.**1 <= Ai, Bi, Ci <= 100000**

In a single line, you have to print the minimum number of Shasthoshommoto Paykhanas they would need to build.

Input | Output |
---|---|

3 2 1 2 1 2 3 2 | 6 |

91% Solution Ratio

msatatm1322Earliest,

MR.Jukerburg11Fastest, 0.0s

msatatm1322Lightest, 131 kB

mdvirusShortest, 100B

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.