개미억장와르르맨션

개미 왕국에는 $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$과 $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$을 출력한다.