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

이 지역에는 가끔 산사태가 발생하는데, 산사태가 발생하여 특정한 도로가 통행 불가능이 될 수 있다. 다행히도 통행 불가능이 되는 경우 오직 하나의 도로만이 그렇게 된다고 한다. 그러한 상황에 대비하기 위해서 각 도로마다, 그 도로가 통행 불가능이 되었다고 가정하고 비상연 락망을 구성할 경우 전체 최소 비용이 얼마가 되는지 알고 싶다.

• 그림-1은 어떤 산골마을의 예이다. 원이 마을이며, 선분이 도로이고, 도로 옆의 수는 그 도로에 해당하는 비용이다.
• 그림-2는 모든 도로가 통행이 가능할 때의 비상 연락망 구성이며, 굵은 선으로 표현된 도로들이 비상연락망에 포함된 것이다. 이때 전체 비용은 13이다.
• 그림-3은 2번과 5번 마을을 잇는 도로가 통행 불 가능인 경우의 비상연락망이며, 비용은 14이다.
• 그림-4는 1번과 2번 마을을 잇는 도로가 통행 불 가능인 경우이며, 비용은 15이다.

수행 시간은 1초를 넘을 수 없다. 메모리 제한은 64MB이다.

입력

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

출력

입출력 예

입력

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

입력

4 4
1 2 1
2 3 2
2 4 3
4 3 2

출력

-1
6
5
6

출처: 제31회 한국정보올림피아드 전국본선 (2014.7.11) 고등부 문제 4