간선 하나를 지운 최소 신장 트리

정점이 $n$개이고 간선이 $m$개인 가중치 무방향 그래프 $G$가 주어진다. 간선에는 $1$번부터 $m$번까지 번호가 붙어 있다.

$G_i$는 $G$에서 $i$번 간선 하나만 지운 그래프다. 각 $i$에 대해 $G_i$의 최소 신장 트리 비용을 구하라.

입력 형식은 다음과 같다.

n m
a1 b1 w1
...
am bm wm

첫째 줄에 정점 수 $n$과 간선 수 $m$이 주어진다 ($2 \le n \le 100{,}000$, $1 \le m \le 200{,}000$).

이어지는 $m$개 줄 중 $i$번째 줄에는 세 정수 $a_i$, $b_i$, $w_i$가 주어진다 ($1 \le a_i \le n$, $1 \le b_i \le n$, $0 \le w_i \le 1{,}000{,}000$). 정점 $a_i$와 정점 $b_i$를 잇는 비용 $w_i$의 간선이 $i$번 간선이라는 뜻이다.

그래프는 단순 그래프임이 보장된다. 즉 두 정점을 잇는 간선은 많아도 하나이고, 모든 $i$에 대해 $a_i \ne b_i$이다.

$m$개 줄에 걸쳐, $i$번째 줄에 $G_i$의 최소 신장 트리 비용을 출력한다. $G_i$에 신장 트리가 없으면 그 줄에는 -1을 출력한다.