Bicycle Race

The Great Bicycle Race is approaching, and the organizers of the annual sports competition need to choose a track for the racers. The country has $n$ cities and $m$ bidirectional roads. The organizers pick one city as the host. The race lasts two days. Each day, riders start at the host city, pass through two intermediate cities, and return to the host city. The intermediate cities must not repeat across the two days, so the race uses five distinct cities and six distinct roads in total. Each road $i$ has an integer attractiveness $a_i$, and the attractiveness of a route is the sum of the six road values. Determine whether a valid race exists, and if so, the maximum possible attractiveness of a route.

The first line contains two integers $n$ and $m$ ($5 \le n \le 100000$, $6 \le m \le 100000$), the number of cities and roads. Each of the next $m$ lines contains three integers $u_i$, $v_i$, and $a_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $1 \le a_i \le 100000$): the two cities connected by road $i$ and its attractiveness. No two roads connect the same pair of cities.

If no valid route exists, print $-1$. Otherwise, print the maximum total attractiveness of a valid route.

In the first sample, one of the best choices is city 5 as the host, with the route 5 → 1 → 2 → 5 → 3 → 4 → 5.