자전거 경주

위대한 자전거 경주 시기가 다가오고 있다. 연례 스포츠 대회 주최 측은 참가자가 달릴 코스를 골라야 한다. 나라에는 $n$개의 도시와 $m$개의 양방향 도로가 있다. 주최 측은 개최 도시를 하나 고른다. 경주는 이틀 동안 진행된다. 매일 선수는 개최 도시에서 출발해 중간 도시 두 곳을 거쳐 다시 개최 도시로 돌아온다. 이틀에 걸쳐 중간 도시가 겹치면 안 되므로, 경주는 서로 다른 도시 다섯 곳과 도로 여섯 개를 지난다. 각 도로 $i$에는 정수 매력도 $a_i$가 있으며, 코스의 매력도는 여섯 도로 값의 합이다. 조건을 만족하는 경주를 열 수 있는지 판단하고, 가능하다면 코스 매력도의 최댓값을 구하라.

첫 줄에 도시 수 $n$과 도로 수 $m$이 주어진다 ($5 \le n \le 100000$, $6 \le m \le 100000$). 다음 $m$개 줄에는 도로 $i$가 잇는 두 도시 $u_i$, $v_i$와 매력도 $a_i$가 주어진다 ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $1 \le a_i \le 100000$). 같은 도시 쌍을 잇는 도로는 없다.

조건을 만족하는 코스가 없으면 $-1$을 출력한다. 그렇지 않으면 가능한 코스 매력도 합의 최댓값을 출력한다.

첫 번째 예시에서 가장 좋은 선택 중 하나는 도시 5를 개최 도시로 삼고, 5 → 1 → 2 → 5 → 3 → 4 → 5 순서로 달리는 것이다.