마을의 특산물 지정

Kickstartia의 시골 지역은 V개의 마을과 이들을 연결하는 E개의 양방향 도로로 이루어져 있다. 주민들은 도로 건설의 다양성을 중시하므로 길이가 같은 두 도로는 없다. 각 도로는 정확히 두 마을을 연결하며, 같은 두 마을을 연결하는 두 도로는 없다.

진보적인 면모를 과시하고 싶어 하는 새 국왕은 각 마을이 과일이나 채소 중 정확히 한 종류의 식품을 전문적으로 생산하도록 계획을 세우려 한다. 어떤 마을이 과일을 생산한다면, 그 마을의 주민들은 채소를 생산하는 어떤 마을까지의 최단 경로를 찾는다. 이 경로에는 여러 도로가 사용될 수도 있다. 마찬가지로 어떤 마을이 채소를 생산한다면, 그 마을의 주민들은 과일을 생산하는 어떤 마을까지의 최단 경로를 찾는다.

모든 일이 원활하게 운영되도록 국왕은 각 마을이 생산하지 않는 식품을 구하기 위해 이동해야 하는 거리의 평균을 최소화하려 한다.

이 평균 거리를 최소화하는 계획은 여러 개일 수 있으므로, 국왕은 그러한 계획이 몇 개인지 알고 싶어 한다. 한 계획에서는 과일을 생산하지만 다른 계획에서는 채소를 생산하는 마을이 하나라도 있으면 두 계획은 서로 다르다. 각 마을이 과일과 채소를 모두 구할 수 있게 하는 계획이 존재함을 국왕이 보장한다.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ E ≤ min(1000, V * (V - 1) / 2). 모든 i에 대해 0 ≤ $L_{i}$ ≤ $10^{5}$. 모든 i ≠ j에 대해 $L_{i}$ ≠ $L_{j}$. 모든 i에 대해 1 ≤ $A_{i}$ < $B_{i}$ ≤ V. 모든 i ≠ j에 대해 ($A_{i}$, $B_{i}$) ≠ ($A_{j}$, $B_{j}$). 모든 마을이 두 종류의 식품을 모두 구할 수 있게 하는 계획이 적어도 하나 존재한다.

소규모 데이터 세트 (테스트 세트 1 - 공개)

2 ≤ V ≤ 10.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

2 ≤ V ≤ 50.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 마을의 수와 도로의 수를 각각 나타내는 두 정수 V와 E가 포함된 한 줄로 시작한다. 마을에는 1부터 V까지 번호가 붙어 있다. 이어서 E개의 줄이 주어진다. 이 줄들 중 i번째 줄에는 세 정수 $A_{i}$, $B_{i}$, $L_{i}$가 주어지며, 이는 i번째 도로가 마을 $A_{i}$와 마을 $B_{i}$를 연결하고 길이가 $L_{i}$임을 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 위에서 설명한 대로 국왕이 원하는 답이다.

예제 케이스 #1에서 가능한 계획 중 하나는 마을 1과 3이 과일을 생산하고 마을 2이 채소를 생산하게 하는 것이다. 마을 1와 2은 자신에게 없는 식품을 구하기 위해 서로에게 이동할 수 있으므로 두 마을 모두 거리 1만큼 이동해야 한다. 마을 3은 채소를 구하기 위해 마을 2까지 이동해야 하며, 이동 거리는 4이다. 따라서 평균 거리는 (1 + 1 + 4)/3 = 2이며, 이는 가능한 최솟값이다. 최적인 다른 계획이 하나 더 있으므로(마을 1과 3이 채소를 생산하고 마을 2이 과일을 생산하는 계획), 최종 답은 2이다.

예제 케이스 #2에는 가능한 계획이 16개 있다. 그중 한 가지는 마을 1, 3, 5이 과일을 생산하고 마을 2, 4, 6이 채소를 생산하게 하는 것이다. 마을 1와 2은 자신에게 없는 식품을 구하기 위해 서로에게 이동해야 한다. 마을 3와 5은 채소를 구하기 위해 마을 4로 이동할 수 있고, 마을 4과 6은 과일을 구하기 위해 마을 3로 이동할 수 있다. 평균 거리는 (6 + 6 + 0 + 1 + 0 + 2)/6 = 2.5이며, 이는 가능한 최솟값인 것으로 밝혀진다. 두 마을이 길이 0인 도로로 연결되어 있더라도 서로 다른 마을로 간주한다.