산골에 N 개의 마을이 있으며 각각 두 마을을 잇는 M 개의 도로가 있다.

이 도로들은 전체 마을들을 모두 연결하고 있다. 즉, 어떤 마을에서든 다른 마을로 (하나 이상의 도로를 거쳐서) 갈 수 있다.

또한 어떤 인접한 두 마을은 두 개 이상의 도로로 바로 연결되기도 한다.

여러 가지 급한 상황이 생길 수 있기 때문에 전체 마을들을 연결하는 비상연락망을 구성하여 급한 상황을 알리기로 하였다.

비상연락망에 들어가는 도로의 경우에는 특별히 잘 관리해야 하므로 각 도로마다 관리 비용이 발생한다.

물론 비상연락망은 전체 관리 비용이 최소가 되도록 만든다.

이 지역에는 가끔 산사태가 발생하는데, 산사태가 발생하여 특정한 도로가 통행 불가능이 될 수 있다.

다행히도 통행 불가능이 되는 경우 오직 하나의 도로만이 그렇게 된다고 한다.

그러한 상황에 대비하기 위해서 각 도로마다, 그 도로가 통행 불가능이 되었다고 가정하고

비상연락망을 구성할 경우 전체 최소 비용이 얼마가 되는지 알고 싶다.

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

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

이때 전체 비용은 13이다.

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

그림-4는 1번과 2번 마을을 잇는 도로가 통행 불가능인 경우이며, 비용은 15이다.

마을의 수와 연결하는 도로들, 그리고 각 도로에 해당하는 비용을 입력으로 받아서

각각의 도로에 대해서 그 도로가 통행 불가능인 경우의 비상연락망을 구성하는 최소 비용을 출력하는 프로그램을 작성하라.

안전한 비상연락망 timer 1초 memory 256MB

안전한 비상연락망 1초 256MB