19852번 - 공정한 회의

먼 미래, SNUPS는 알고리즘 교육 열풍에 힘입어 총 $N$명의 회원이 존재하는 큰 동아리가 되었다. 모든 서로 다른 두 회원 사이에는 친밀한 정도를 나타내는 “친밀 거리”를 정의할 수 있다. $i$번 회원과 $j$번 회원 사이의 친밀 거리는 정수 $C(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$번 회원의 의견이 반영되지 못하고, 이러한 경우 회의가 불공정하다고 한다.

제연이는 어떤 세 명이 회의를 진행하더라도 불공정한 경우가 생기지 않게끔 하고 싶다. 다행히도 SNUPS는 커질 대로 커져, $M$쌍의 회원을 제외하고는 아직 서로 모르는 상태이다. 이미 서로 아는 회원들 사이의 친밀 거리를 바꿀 수는 없지만, 서로 모르는 회원들 간의 친밀 거리를 원하는 대로 조정하는 것은 인간 심리에 통달한 제연이에게는 무척 간단한 일이다. 물론 최종적으로 정해진 친밀 거리는 $1\le i, j\le N, i\ne j$에 대해 $1\le C(i,j)\le 10^7$, $C(i,j)=C(j,i)$를 만족하는 정수여야 한다.

만약 이러한 계획이 실현 가능하다면, 친밀한 SNUPS를 위해 $\sum_{i=1}^{N}{\sum_{j=i+1}^{N}{C(i,j)}}$를 최소로 만들려고 한다. SNUPS의 밝은 미래를 위해 제연이의 계획이 실현 가능한지 판단하고, 가능하다면 $\sum_{i=1}^{N}{\sum_{j=i+1}^{N}{C(i,j)}}$의 최솟값을 구하자.

입력의 첫 줄에는 회원의 수 $N$, 이미 서로를 알고 있는 관계의 수 $M$이 주어진다.

둘째 줄부터 $M$개의 줄에 걸쳐 회원들의 관계에 대한 정보가 주어진다. $i+1$번째 줄에는 세 개의 정수 $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 \neq j$에 대해 $\{A_{i}, B_{i}\} \neq \{A_{j}, B_{j}\}$
• $1 \le D_{i} \le 10^{7}$