407306: GYM102759 D Just Meeting

SNUPS is the programming contest club of Seoul National University. There are $$$N$$$ members in the club, and for every two distinct members $$$1 \le i, j \le N, i \neq j$$$, we define the friend distance $$$C(i, j)$$$. The friend distance is symmetric ($$$C(i, j) = C(j, i)$$$ for all $$$i \neq j$$$), and is an integer in range $$$[1, 10^7]$$$. The smaller the friend distance is, the more friendly two members are toe each other.

When there is an agenda to discuss in SNUPS, they select three distinct members uniformly at random and the three members hold a discussion. However, if $$$C(i, j) < C(j, k)$$$ and $$$C(i, j) < C(i, k)$$$ for the three members $$$i, j, k$$$ in discussion, then members $$$i$$$ and $$$j$$$ may collude and ignore member $$$k$$$. We call this an unjust meeting.

Currently, there are $$$M$$$ pairs of friends, and their friend distance can not be changed. All other pairs of members can have their friend distances changed. Sunghyeon will hold a party for the SNUPS members and change the friend distances for all of these pairs. After the party, the friend distance should satisfy the symmetry condition and should be an integer in range $$$[1, 10^7]$$$.

Sunghyeon wants to know if he can set the friend distance in such a way that it is impossible to have an unjust meeting. If this is possible, he also wants to minimize $$$\sum_{i=1}^{N}{\sum_{j=i+1}^{N}{C(i,j)}}$$$ in order to make the club as friendly as possible.

The first line contains two space-separated integers $$$N, M$$$. ($$$3 \le N \le 300\,000, 0 \le M \le 300\,000$$$).

The next $$$M$$$ lines contains three space-separated integers $$$A_i, B_i, D_i$$$. This means that the member $$$A_i$$$ and $$$B_i$$$ are friends, and have a friend distance of $$$D_i$$$. ($$$1 \le A_i, B_i \le N, 1 \le D_i \le 10^7, A_i \neq B_i$$$).

These $$$M$$$ lines describe exactly all friends in SNUPS, and no pair of friends is described more than once. Formally, for all $$$1 \le i \neq j \le M$$$, $$$\{A_{i}, B_{i}\} \neq \{A_{j}, B_{j}\}$$$.

Print -1 if Sunghyeon's plan is not satisfiable. Otherwise, print the minimum possible value of $$$\sum_{i=1}^{N}\sum_{j = i+1}^{N} C(i,j)$$$.

4 2
1 2 5
2 4 3

14

4 4
1 2 10
1 3 20
2 4 30
3 4 40

-1