문제
산골에 N 개의 마을이 있으며 각각 두 마을을 잇는 M 개의 도로가 있다.
이 도로들은 전체 마을들을 모두 연결하고 있다. 즉, 어떤 마을에서든 다른 마을로 (하나 이상의 도로를 거쳐서) 갈 수 있다.
또한 어떤 인접한 두 마을은 두 개 이상의 도로로 바로 연결되기도 한다.
여러 가지 급한 상황이 생길 수 있기 때문에 전체 마을들을 연결하는 비상연락망을 구성하여 급한 상황을 알리기로 하였다.
비상연락망에 들어가는 도로의 경우에는 특별히 잘 관리해야 하므로 각 도로마다 관리 비용이 발생한다.
물론 비상연락망은 전체 관리 비용이 최소가 되도록 만든다.
이 지역에는 가끔 산사태가 발생하는데, 산사태가 발생하여 특정한 도로가 통행 불가능이 될 수 있다.
다행히도 통행 불가능이 되는 경우 오직 하나의 도로만이 그렇게 된다고 한다.
그러한 상황에 대비하기 위해서 각 도로마다, 그 도로가 통행 불가능이 되었다고 가정하고
비상연락망을 구성할 경우 전체 최소 비용이 얼마가 되는지 알고 싶다.
그림-1은 어떤 산골마을의 예이다. 원이 마을이며, 선분이 도로이고, 도로 옆의 수는 그 도로에 해당하는 비용이다.
그림-2는 모든 도로가 통행이 가능할 때의 비상연락망 구성이며, 굵은 선으로 표현된 도로들이 비상연락망에 포함된 것이다.
이때 전체 비용은 13이다.
그림-3은 2번과 5번 마을을 잇는 도로가 통행 불가능인 경우의 비상연락망이며, 비용은 14이다.
그림-4는 1번과 2번 마을을 잇는 도로가 통행 불가능인 경우이며, 비용은 15이다.
마을의 수와 연결하는 도로들, 그리고 각 도로에 해당하는 비용을 입력으로 받아서
각각의 도로에 대해서 그 도로가 통행 불가능인 경우의 비상연락망을 구성하는 최소 비용을 출력하는 프로그램을 작성하라.
입력
입력의 첫 줄에는 마을의 수 N ( 2 ≤ N ≤ 100,000 )과 도로의 수 M ( 2 ≤ M ≤ 300,000 )이 자연수로 주어진다.
각 마을은 1번부터 번호가 붙은 것으로 생각한다.
이후 M 개의 줄에는 각각 3개의 자연수가 주어지는데, 첫 두 자연수는 해당 도로가 잇는 두 마을의 번호이며,
세 번째 자연수는 그 도로가 비상연락망에 포함될 경우의 관리 비용이다. 비용은 0 이상 109이하이다.
하나의 마을 쌍에 대해 여러 개의 도로가 존재할 수도 있으며, 서로 다른 도로가 같은 비용 값을 가질 수도 있음에 주의하라.
출력
출력에는 M 개의 줄이 있어야하며, 각 줄에는 하나의 자연수가 있어야 한다.
i 번째 줄에는 입력에 i 번째로 주어진 도로가 통행 불가능인 경우 비상연락망의 최소 비용을 자연수로 출력한다.
단, 비상연락망이 존재하지 않는다면 -1을 출력해야 한다.
비용의 값이 커질 수 있으므로 64비트 정수 변수(long long type)를 사용해야 할 수도 있음에 주의하라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 7점 | N ≤ 5, M ≤ 10 |
| #2 | 16점 | N ≤ 100, M ≤ 1,000 |
| #3 | 11점 | N ≤ 1,000, M ≤ 10,000 |
| #4 | 27점 | N ≤ 5,000, M ≤ 20,000 |
| #5 | 39점 | 원래의 제약조건 이외에 아무 제약조건이 없다. |
예제1
5 9
1 2 1
3 1 4
4 3 6
2 4 7
2 5 2
5 3 5
1 5 3
5 4 7
2 4 8
15
14
14
13
14
13
13
13
13
예제2
4 4
1 2 1
2 3 2
2 4 3
4 3 2
-1
6
5
6