Practice on Toph

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

Meena Meets The Marauders

By raida_ash · Limits 500ms, 1.5 GB

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.

Input

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

Output

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

Sample

InputOutput
3 2
1 2 1
2 3 2
6


Discussion
Statistics

90% Solution Ratio

msatatm1322Earliest, Aug '17

Black_mambaFastest, 0.0s

msatatm1322Lightest, 131 kB

mdvirusShortest, 100B

Submit

Login to submit