네트워크 연결

넓은 지역에 있는 특정 지점들을 잇는 네트워크 연결을 설계하려고 한다. 지역 안의 지점들의 집합과, 지점 쌍을 연결할 수 있는 케이블 경로들의 집합이 주어진다. 두 지점을 잇는 각 경로마다, 그 경로를 따라 두 지점을 연결하는 데 필요한 케이블의 길이가 주어진다. 두 지점 사이에 여러 개의 경로가 있을 수도 있음에 유의하라. 주어진 경로들은 지역 안의 임의의 두 지점을 (직접 또는 간접적으로) 연결한다고 가정한다.

임의의 두 지점 사이에 (직접 또는 간접적인) 연결이 존재하도록, 즉 모든 지점이 서로 연결되도록(반드시 직접 케이블로 연결될 필요는 없다) 하면서 사용하는 케이블의 총 길이가 최소가 되도록 네트워크를 설계하는 것이 문제이다.

입력은 여러 개의 데이터 세트로 이루어지며, 각 데이터 세트는 하나의 네트워크를 정의한다. 각 데이터 세트의 첫째 줄에는 두 정수가 주어지는데, 첫 번째는 지점의 수 $P$이고 두 번째는 지점들 사이 경로의 수 $R$이다. 이어지는 $R$개의 줄에는 각 경로가 세 정수로 주어진다. 앞의 두 정수는 두 지점을 나타내고, 세 번째 정수는 그 경로의 길이이다. 수들은 공백으로 구분된다. 하나의 수 $P = 0$만으로 이루어진 데이터 세트는 입력의 끝을 나타낸다. 데이터 세트는 빈 줄로 구분된다.

지점의 수는 최대 $50$개이다. 한 경로의 최대 길이는 $100$이다. 가능한 경로의 수에는 제한이 없다. 지점은 $1$부터 $P$까지(포함)의 정수로 구분된다. 두 지점 $i$와 $j$ 사이의 경로는 i j 또는 j i로 주어질 수 있다.

각 데이터 세트에 대해, 설계한 전체 네트워크에서 사용한 케이블의 총 길이를 한 줄에 하나의 수로 출력한다.