공정한 회의

먼 미래, SNUPS는 알고리즘 교육 열풍에 힘입어 회원이 총 $N$명인 큰 동아리가 되었다. 서로 다른 두 회원 사이에는 친밀한 정도를 나타내는 친밀 거리를 정의할 수 있으며, 값이 작을수록 더 친밀하다는 뜻이다. $i$번 회원과 $j$번 회원 사이의 친밀 거리는 정수 $C(i,j)$로 나타낸다. 모든 $1\le i, j\le N$, $i\ne j$에 대해 $1\le C(i,j)\le 10^7$이고 $C(i,j)=C(j,i)$를 만족한다.

안건이 생길 때마다 SNUPS는 회원 $N$명 가운데 무작위로 세 명을 뽑아 회의를 진행한다. 뽑힌 세 명 중 친한 두 명이 연합하면 나머지 한 명의 의견이 반영되지 않는다. 구체적으로, 뽑힌 서로 다른 세 회원을 각각 $i$, $j$, $k$번 회원이라 할 때 $C(i,j) < C(j,k)$이고 $C(i,j) < C(i,k)$이면 $k$번 회원의 의견이 반영되지 못한다. 이때 회의가 불공정하다고 한다.

제연이는 어떤 세 명이 회의를 하더라도 불공정한 경우가 생기지 않게 하고 싶다. 현재 $M$쌍의 회원만 서로 알고 있고 나머지 회원끼리는 아직 모른다. 이미 아는 사이의 친밀 거리는 바꿀 수 없지만, 모르는 사이의 친밀 거리는 원하는 대로 정할 수 있다. 최종 친밀 거리도 정수이면서 위 범위와 대칭 조건을 만족해야 한다.

이러한 계획이 실현 가능하다면 $\sum_{i=1}^{N}\sum_{j=i+1}^{N} C(i,j)$를 최소로 만드는 것이 목표이다. 계획이 실현 가능한지 판단하고, 가능하다면 이 값의 최솟값을 구하라.

첫 줄에 회원의 수 $N$과 이미 서로 아는 관계의 수 $M$이 주어진다. 둘째 줄부터 $M$개의 줄에 걸쳐 세 정수 $A_i$, $B_i$, $D_i$가 공백으로 구분되어 주어진다. 이는 $A_i$번 회원과 $B_i$번 회원이 이미 아는 사이이며, 둘의 친밀 거리가 $D_i$라는 뜻이다.

계획이 실현 불가능하면 -1을, 가능하면 $\sum_{i=1}^{N}\sum_{j=i+1}^{N} C(i,j)$의 최솟값을 출력한다.

• $3 \le N \le 300,000$
• $0 \le M \le 300,000$
• $1 \le A_i, B_i \le N$, $A_i \ne B_i$, $i \ne j$일 때 $\{A_i, B_i\} \ne \{A_j, B_j\}$
• $1 \le D_i \le 10^{7}$