안전한 비상연락망

산골에 마을 $N$개가 있고, 두 마을을 잇는 도로 $M$개가 있다. 이 도로들은 모든 마을을 연결한다. 즉 어느 마을에서 출발하더라도 도로를 하나 이상 거쳐 다른 모든 마을에 갈 수 있다. 인접한 두 마을이 도로 두 개 이상으로 곧바로 이어져 있기도 하다.

급한 상황을 빠르게 알리려고 모든 마을을 잇는 비상연락망을 만들기로 했다. 비상연락망에 들어가는 도로는 특별히 관리해야 하므로 도로마다 관리 비용이 든다. 비상연락망은 전체 관리 비용이 최소가 되도록 구성한다.

이 지역에는 가끔 산사태가 나고, 그 때문에 도로 하나가 통행 불가능이 되기도 한다. 통행 불가능이 되는 도로는 많아야 하나다.

각 도로마다 그 도로 하나만 통행 불가능이 되었다고 가정하고, 남은 도로로 비상연락망을 구성할 때의 최소 관리 비용을 구하라. 남은 도로만으로 모든 마을을 연결할 수 없다면 그 도로의 답은 -1이다.

첫 줄에 마을의 수 $N$ (2 ≤ $N$ ≤ 100,000)과 도로의 수 $M$ (2 ≤ $M$ ≤ 300,000)이 주어진다. 마을 번호는 1번부터 $N$번까지다.

이어지는 $M$개의 줄에는 각각 자연수 세 개가 주어진다. 앞의 두 수는 그 도로가 잇는 두 마을의 번호이고, 세 번째 수는 그 도로가 비상연락망에 포함될 때의 관리 비용이다. 비용은 1 이상 $10^9$ 이하다. 한 마을 쌍을 잇는 도로가 여러 개일 수 있고, 서로 다른 도로의 비용이 같을 수도 있다.

$M$개의 줄을 출력한다. $i$번째 줄에는 입력에서 $i$번째로 주어진 도로가 통행 불가능일 때 비상연락망의 최소 관리 비용을 출력한다. 그런 비상연락망이 없으면 -1을 출력한다.

비용의 합이 32비트 정수 범위를 넘을 수 있으니 64비트 정수를 써야 할 수도 있다.