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, . To develop the map, they needed information about the set of corridors, . 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 Lifebuoy Soaps in order to learn about the corridor from to . The misery doesn’t end there. For each corridor that goes from place to place the Marauders need to pay Lifebuoy Soaps to go from to , and also when they go from to .
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.
In a single line, you will be given and (), the number of nodes and the number of corridors respectively.
In the next lines, you will be given three integers, , and . This means that it is possible to go from to with () Lifebuoy soaps. It is also possible to go from to with Lifebouy Soaps.
In a single line, you have to print the minimum number of Lifebuoy Soaps they would need to pay.
Input | Output |
---|---|
3 2 1 2 1 2 3 2 | 6 |