문제 링크 - https://www.acmicpc.net/problem/1647문제에서 구하라고 하는 것을 요약하면, 최소 스패닝 트리를 구해서 간선 비용 합의 최솟값을 구하는 것이다.이때 마을을 두개로 분할해야 하는데, 문제를 읽어보면 별 다른 조건 없이 두