Fair Meeting

In the distant future, SNUPS has grown into a large club of $N$ members, driven by a boom in algorithm education. Any two distinct members can be assigned a closeness distance, an integer $C(i,j)$ where a smaller value means the two are closer. For all $1\le i, j\le N$ with $i\ne j$, $1\le C(i,j)\le 10^7$ and $C(i,j)=C(j,i)$.

Each time an agenda item comes up, SNUPS picks three of the $N$ members at random to hold the meeting. When two of the three who are close join forces, the third member's opinion is not reflected. Concretely, if the three distinct members picked are $i$, $j$, and $k$, and $C(i,j) < C(j,k)$ and $C(i,j) < C(i,k)$, then member $k$'s opinion is not reflected. Such a meeting is called unfair.

Jeyeon wants to make sure no unfair meeting can happen for any three members. So far, only $M$ pairs of members know each other. The distances of known pairs cannot change, but Jeyeon can set the distances of unknown pairs as she likes. The final distances must still be integers within range and symmetric.

If such a plan is feasible, the goal is to minimize $\sum_{i=1}^{N}\sum_{j=i+1}^{N} C(i,j)$. Determine whether the plan is feasible, and if it is, find the minimum value of this sum.

The first line contains $N$ and $M$. Each of the next $M$ lines contains three integers $A_i$, $B_i$, and $D_i$, meaning members $A_i$ and $B_i$ already know each other and their closeness distance is $D_i$.

Print -1 if the plan cannot be carried out. Otherwise, print the minimum value of $\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$, and $\{A_i, B_i\} \ne \{A_j, B_j\}$ for $i \ne j$
• $1 \le D_i \le 10^{7}$