10169번 - 안전한 비상연락망 서브태스크

산골에 N 개의 마을이 있으며 각각 두 마을을 잇는 M 개의 도로가 있다. 이 도로들은 전체 마을들을 모두 연결하고 있다. 즉, 어떤 마을에서든 다른 마을로 (하나 이상의 도로를 거쳐서) 갈 수 있다. 또한 어떤 인접한 두 마을은 두 개 이상의 도로로 바로 연결되기도 한다. 여러 가지 급한 상황이 생길 수 있기 때문에 전체 마을들을 연결하는 비상연락망을 구성하여 급한 상황을 알리기로 하였다. 비상연락망에 들어가는 도로의 경우에는 특별히 잘 관리해야 하므로 각 도로마다 관리 비용이 발생한다. 물론 비상연락망은 전체 관리 비용이 최소가 되도록 만든다.

이 지역에는 가끔 산사태가 발생하는데, 산사태가 발생하여 특정한 도로가 통행 불가능이 될 수 있다. 다행히도 통행 불가능이 되는 경우 오직 하나의 도로만이 그렇게 된다고 한다. 

그러한 상황에 대비하기 위해서 각 도로마다, 그 도로가 통행 불가능이 되었다고 가정하고 비상연락망을 구성할 경우 전체 최소 비용이 얼마가 되는지 알고 싶다.

그림-1

그림-1은 어떤 산골마을의 예이다. 원이 마을이며, 선분이 도로이고, 도로 옆의 수는 그 도로에 해당하는 비용이다. 

그림-2

그림-2는 모든 도로가 통행이 가능할 때의 비상연락망 구성이며, 굵은 선으로 표현된 도로들이 비상연락망에 포함된 것이다. 이때 전체 비용은 13이다.

그림-3

그림-3은 2번과 5번 마을을 잇는 도로가 통행 불가능인 경우의 비상연락망이며, 비용은 14이다. 그림-4는 1번과 2번 마을을 잇는 도로가 통행 불가능인 경우이며, 비용은 15이다.

그림-4

마을의 수와 연결하는 도로들, 그리고 각 도로에 해당하는 비용을 입력으로 받아서 각각의 도로에 대해서 그 도로가 통행 불가능인 경우의 비상연락망을 구성하는 최소 비용을 출력하는 프로그램을 작성하라.

입력의 첫 줄에는 마을의 수 N (2 ≤ N ≤ 100,000)과 도로의 수 M (2 ≤ M ≤ 300,000)이 자연수로 주어진다. 각 마을은 1번부터 번호가 붙은 것으로 생각한다. 이후 M 개의 줄에는 각각 3개의 자연수가 주어지는데, 첫 두 자연수는 해당 도로가 잇는 두 마을의 번호이며, 세 번째 자연수는 그 도로가 비상연락망에 포함될 경우의 관리 비용이다. 비용은 1 이상 10⁹ 이하이다. 하나의 마을 쌍에 대해 여러 개의 도로가 존재할 수도 있으며, 서로 다른 도로가 같은 비용 값을 가질 수도 있음에 주의하라.

출력에는 M개의 줄이 있어야하며, 각 줄에는 하나의 자연수가 있어야 한다. I 번째 줄에는 입력에 I 번째로 주어진 도로가 통행 불가능인 경우 비상연락망의 최소 비용을 자연수로 출력한다. 단, 비상연락망이 존재하지 않는다면 -1을 출력해야 한다. 비용의 값이 커질 수 있으므로 64비트 정수 변수(long long type)를 사용해야 할 수도 있음에 주의하라.