Eternal Embers

Chad was a firefighter, a very good one at that. Not only was he good at extinguishing fires, he also knew the city’s design by heart. This made him able to find the fastest route from the fire station to anywhere else in the city quite quickly, saving a lot of lives.

But Chad was mean-spirited when he was not firefighting. He frequently stole bus seats from old ladies, vacuumed his apartment at $6$ AM on Sundays, and replaced all the sugar at work with salt.

So it was a tough choice for the Maker when They had to decide whether Chad should get to go Upstairs or Downstairs. Clearly, the lives he had saved outweighed his mean-spiritedness, but it would not be good for the community Upstairs if Chad became a member. The Maker decided therefore that Chad should go Downstairs. Whether this is morally the right choice or not is outside of the scope of this problem.

As the worst thing Chad did was being mean to other people, the rulers of the Downstairs decided to let Chad get off easy: They gave Chad a fire hose with infinite capacity, set up some pits with eternal flames, and then tasked him to extinguish the flames. But the fires would only turn into eternal embers, which would turn back into eternal flames again after exactly $A$ seconds! If he weren’t able keep them all extinguished $A$ seconds after his work shift started until the work shift ended, he would receive severe punishment: No shower that day.

Chad is still good at extinguishing fires, using no time at all to do so. However, he was never told $A$, has no knowledge of the Downstair’s layout, and tended to wander all over the place. After some weeks, the unfortunate canteen imps couldn’t handle his odour anymore and gave Chad some hints on how he would be able to shower. They gave him a map over the Downstairs, and although they didn’t know what $A$ is, they knew how it was computed: $A$ is exactly the time it takes to visit all the flames in the shortest amount of time, and return back to the main office.

Chad always starts the workday by extinguishing the eternal flames right outside the main office. Can you help Chad find the length of the optimal route, so that the poor imps can regain a health and safety-compliant work environment?


The first line contains three integers, $N$, $|V|$ and $|E|$, denoting the number of eternal flame pits, the number of locations, and the number of paths between the locations. The flame pits are situated at locations numbered $0\ldots N-1$, main office is situated at location $0$.

Then follow $|E|$ lines, each representing a path between two locations. Each line contains three integers, $u_ i$, $v_ i$ and $w_ i$, denoting the two locations and the time it takes to walk from one location to the other in seconds. It is possible to walk both from $u_ i$ to $v_ i$ and vice versa.


Output $A$, the length of the optimal route as described above.


  • $0 < N \leq 12$

  • $N \leq |V| \leq 300$

  • $|V| - 1 \leq |E| \leq |V|^2$

  • $0 \leq u_ i < v_ i < |V|$

  • $0 < w_ i \leq 1\, 000$

  • $G = (V, E)$ forms a fully-connected undirected graph.

Sample Input 1 Sample Output 1
3 5 5
0 4 6
1 4 7
1 3 6
2 3 7
2 4 5