통행료 인상하기

ICPC 왕국은 $1$번부터 $N$번까지 번호가 붙은 $N$개의 도시로 이루어진 큰 나라입니다. ICPC 왕국의 매력은 아름다운 경치에 있습니다. 국왕은 그 경치를 알리기 위해 관광객이 즐길 수 있는 경치 좋은 곳 근처에 $1$번부터 $M$번까지 번호가 붙은 $M$개의 유료 도로를 만들기로 했습니다. 도로 $i$는 도시 $U_i$와 $V_i$를 양방향으로 잇고, 이용하려면 $W_i$를 내야 합니다. 이 도로들로 어느 도시에서든 다른 모든 도시로 갈 수 있습니다.

유료 도로는 이미 건설되어 이용할 수 있지만 아직 관광객을 끌지 못합니다. 국왕은 홍보책을 내놓았습니다. 이용하고 싶은 도로의 요금을 미리 내 두면, ICPC 왕국 밖으로 나가지 않는 한 그 도로를 여러 번 이용할 수 있습니다.

이 방식으로 관광객은 모였지만 이상한 현상이 나타났습니다. 모든 관광객은 어느 도시에서든 다른 모든 도시로 갈 수 있게 해 주는 도로 집합 중 총 요금이 가장 적은 집합에 대해서만 돈을 냅니다. 현재 요금에서는 이런 도로 집합이 하나로 정해집니다. 이 이상한 행동 때문에 관광객은 왕국의 경치를 충분히 보지 못합니다.

더 많은 경치를 보여 주기 위해 국왕은 일부 도로의 요금을 올리기로 했습니다. 요금을 올리기 전에 이상한 행동에서 쓰이던 도로 $i$는, 요금을 올린 뒤에는 그 행동에서 반드시 쓰이지 않도록 해야 합니다. 국왕은 전체 도로의 요금 인상액 합이 가능한 한 작기를 원합니다.

국왕의 계획을 달성하기 위한 최소 총 인상액을 구하고, 계획이 불가능하면 그 사실을 알려 주세요.

첫 줄에 도시 수 $N$과 도로 수 $M$이 주어집니다 ($2 \le N \le 100\,000$; $N - 1 \le M \le 200\,000$). 이어지는 $M$개의 줄에는 정수 세 개 $U_i$, $V_i$, $W_i$가 주어집니다 ($1 \le U_i < V_i \le N$; $1 \le W_i \le 10^9$). 이는 도로 $i$가 도시 $U_i$와 $V_i$를 요금 $W_i$로 잇는다는 뜻입니다. 요금을 올리기 전에는 어느 두 도시 사이든 총 요금이 최소가 되도록 이동하게 하는 도로 집합이 하나로 정해집니다.

국왕의 계획을 달성할 수 있으면 최소 총 인상액을 정수 하나로 출력합니다. 그렇지 않으면 -1을 한 줄에 출력합니다.