우주 제국의 황제 명우는 최근 서로 전쟁을 하던 N개 행성을 어부지리로 점령했다.

이제 이 N개의 행성에는 평화가 찾아왔다.

여기에 더해서 명우는 N개 행성 간에 서로 이동이 가능하도록 N−1쌍의 워프 게이트를 설치하려고 한다.

하나의 워프 게이트를 설치하면 두 행성간의 이동이 가능하며,

어떤 행성들을 어떤 방식으로 연결하느냐에 따라 비용의 차이가 있을 수 있다.

명우는 현재 총 M가지 쌍의 워프 게이트를 연결할 수 있다.

명우는 N개의 행성 중 하나를 골라 주요 행성으로 삼아 자신의 우주 제국과 연결되는 워프 게이트를 만들 것이다.

명우는 선택된 주요 행성과 연결되는 워프 게이트를 비용을 따지지 않고 최대한 많이 만들고 싶다.

각각의 행성을 주요 행성으로 삼을 때 N−1개의 워프 게이트를 설치하는 비용의 최솟값을 구하는 프로그램을 작성하라.

Logistical Metropolis timer 3s memory 512MB

Logistical Metropolis 3s 512MB