28133번 - 개미억장와르르맨션

개미 왕국에는 $N+1$개의 개미굴이 있으며, 각 개미굴은 $0$번부터 $N$번까지 차례대로 번호가 붙어 있다. 또한 서로 다른 두 개미굴을 연결하는 $M$개의 양방향 길이 있다. 어느 날 폭우가 쏟아진 이후, 개미 왕국은 붕괴 위기에 처하게 되어 모든 길의 붕괴 위험도를 측정하였다. $i$번 길의 붕괴 위험도는 $d_{i}$로 나타낸다. 기본적으로 모든 길은 서로 다른 위험도를 가지고 있다. 하지만 예외적으로 $0$번 개미굴과 직접 이어진 길들은 서로 같은 위험도를 가질 수 있다.

그렇다면 개미굴은 안전할까?

현재 $0$번 개미굴에 $1$번부터 $N$번까지 번호가 붙은 $N$마리의 개미가 모여있다. $i$번 개미는 $i$번 개미굴이 안전한지 확인하기 위한 여정을 떠난다. 이때 개미들은 여정에서 이용할 길들의 위험도 합을 최소화하여 이동하고자 한다. 다시 말해 $N$마리의 개미가 이용할 길 번호들의 집합이 $S=\{s_{1}, s_{2},\cdots, s_{M}\}$일 때, 다음의 값 $W$를 최소화하고자 한다.

$$ W=\sum_{i=1}^{M}{d_{s_{i}}} $$

개미는 하나의 길을 이용할 때마다 $1$만큼의 체력을 소모한다. $W$가 최소일 때, $N$마리의 개미들이 소모할 체력의 합이 최소가 되도록 개미들을 도와주자.

첫째 줄에는 $N$과 $M$이 공백을 두고 주어진다. $(1\leq N \leq 200\,000; 1 \leq M \leq 200\,000)$

이후 $M$개의 줄에는 길의 정보 $u$, $v$, $d$가 공백을 두고 주어진다. $u$번 개미굴과 $v$번 개미굴을 연결하는 길이 $d$만큼의 위험도를 가지고 있다는 뜻이다. $(0\leq u,v \leq N; u \neq v; 1\leq d \leq 10^{9})$

$W$가 최소일 때, 개미들이 소모할 체력의 합의 최솟값을 출력하시오. 단, $N$개의 개미굴을 모두 점검할 수 없다면 $-1$을 출력한다.