고속철도망 설계하기

N개의 도시가 있는 나라에서 모든 도시가 고속철도망으로 서로 연결되도록 하려고 한다.

일부 도시 쌍에는 이미 고속철도가 설치되어 있다. 이미 설치된 노선은 철거하지 않으며, 그 비용도 전체 사업 비용에 포함한다. 아직 연결되지 않은 도시 쌍에는 주어진 비용을 내고 새 고속철도를 설치할 수 있다.

새 노선을 적절히 추가하여 임의의 도시에서 다른 임의의 도시로 고속철도만 이용해 이동할 수 있게 만들 때, 전체 비용의 최솟값과 새로 설치한 노선들을 구하라.

첫째 줄에 도시의 수 N이 주어진다. (1 <= N <= 200)

다음 N개의 줄에는 N개의 정수가 주어지며, 이는 도시 쌍 사이의 비용을 나타내는 인접행렬이다. 각 비용의 절댓값은 10,000을 넘지 않는다. 두 도시 사이의 값이 음수이면 그 두 도시 사이에는 이미 고속철도가 설치되어 있으며, 그 비용은 해당 값의 절댓값이다. 양수이면 아직 설치되지 않았고, 그 값을 비용으로 내면 새 노선을 설치할 수 있다.

첫째 줄에 두 정수 C와 M을 출력한다. C는 이미 설치된 고속철도와 새로 설치한 고속철도를 모두 포함한 최소 총비용이고, M은 새로 설치한 고속철도의 개수이다.

다음 M개의 줄에는 새로 고속철도를 설치한 두 도시 번호를 한 줄에 하나씩 출력한다.