Problem B
Bamboozled Boardwalk

Picture by Daniel SeSSler

Success! Benjamin and his bridge and boardwalk building company Bridgesmith has gotten the contract to improve accessibility to nature around the town of Wildeley. The area has many beautiful locations, but all are rather inaccessible as they are surrounded by a big bog. To make them easily accessible, the town’s mayor has decided that it should be possible to reach all of these “islands” by walking over boardwalks. There are many possible ways to connect these islands, so Bridgesmith has sent in a lot of boardwalk alternatives to Wildeley’s mayor.

Unfortunately, the recent recession has also impacted Wildeley, and not as many tourists can afford to go there anymore. While the initial plans were more grandiose, the mayor has decided that they will only pick the cheapest boardwalks to connect all the “islands”, and no more. It will still be a good sum of money and work for years to come, but not as much as Bridgesmith hoped for.

Benjamin has an idea though. Since Bridgesmith’s profits are purely derived from the cost of their projects, driving the total cost up will bring in more profits. And although they have delivered all the alternatives over to the mayor, they can say that one of the alternatives has a grave error and must be retracted. But to not raise any suspicion and reopen the bidding process, at most one such retraction can be done.

Benjamin isn’t entirely sure which boardwalk they should retract, however, as there are a lot of these “islands”, and Bridgesmith has proposed a lot of boardwalk alternatives. Can you help Benjamin find which boardwalk they should retract (if any)?

Input

The first line contains two integers $V$ and $B$, the number of “islands” (including the mainland) and the number of boardwalk proposals Bridgesmith has submitted to the mayor. Then follows $B$ lines, one per boardwalk proposal, each with three integers $u_ i$, $v_ i$ and $c_ i$ each:

• $u_ i$ and $v_ i$ are the “bog islands” this boardwalk will connect

• $c_ i$ is the cost of building this boardwalk

Output

Output the maximal total cost of all the boardwalks Wildeley wants to contract, assuming Bridgesmith can retract at most $1$ boardwalk alternative.

Limits

• $1 < V \leq 250$

• $0 \leq u_ i, v_ i < V$ and $u_ i \neq v_ i$

• $0 < c_ i \leq 10\, 000$

• $V - 1 \leq B \leq V^{2}$

• The graph formed by $G = (V, B)$ is connected.

5 6
0 1 10
0 2 3
0 3 8
0 4 9
1 2 6
3 4 4

28

4 6
1 0 2
1 3 8
1 2 4
0 2 3
3 1 7
2 3 5

12