🔈 문제 민식이는 여름에 유럽여행을 떠날 계획이다. 방문할 나라는 총 N개의 나라이고 편리하게 1번부터 N번까지 번호를 붙였다. 또한 이 나라들 사이에 이동 가능한 길은 M개가 있는데 민식이는 귀찮기 때문에 N개의 나라가 서로 연결된 것을 유지시키면서 최대한 많은 길을 지도에서 제거하고자 한다. 즉, N-1개의 길만을 남겨야할 것이다. 각 길을 통과하기 위한 비용이 각기 다르고 한 나라를 도착하면 내야할 비용 역시 나라마다 다르게 정해져있다. 민식이는 모든 도시를 최소 한번 이상 방문하면서 최소 비용이 드는 방법을 찾고 있다. 물론 길과 나라는 여러 번 방문할 수 있고, 첫 시작 나라는 민식이가 정할 수 있고, 마지막 나라는 시작 나라이어야 한다. 이러한 민식이의 유럽 계획을 도와주자. 📝입력 첫 줄에는..