마을 특화

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

진보성을 과시하고 싶은 새 왕은 각 마을이 과일이나 채소 중 정확히 한 가지 식품을 생산하는 계획을 세우려 한다. 어떤 마을이 과일을 생산한다면, 그 마을은 채소를 생산하는 어떤 마을까지의 최단 경로를 찾는다(여러 도로를 거칠 수 있다). 마찬가지로 어떤 마을이 채소를 생산한다면, 그 마을은 과일을 생산하는 어떤 마을까지의 최단 경로를 찾는다.

원활한 운영을 위해, 왕은 각 마을이 자신이 생산하지 않는 식품을 얻기 위해 이동해야 하는 거리의 평균을 최소화하려 한다.

이 평균 거리를 최소화하는 계획은 여러 가지가 있을 수 있으므로, 왕은 그 개수를 알고 싶어 한다. 두 계획은 한 마을이 한 계획에서는 과일을 생산하고 다른 계획에서는 채소를 생산하면 서로 다르다. 왕은 모든 마을이 과일과 채소를 모두 얻을 수 있는 계획이 존재함을 보장한다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 두 정수 V와 E가 주어진다. 이는 각각 마을의 수와 도로의 수이다. 마을에는 1부터 V까지 번호가 붙어 있다. 이어서 E개의 줄이 주어진다. 이 중 i번째 줄에는 세 정수 Ai, Bi, Li가 주어지는데, i번째 도로가 마을 Ai와 Bi를 연결하고 길이가 Li임을 뜻한다.

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

• 1 ≤ T ≤ 100.
• 1 ≤ E ≤ min(1000, V * (V - 1) / 2).
• 0 ≤ Li ≤ 105, for all i.
• Li ≠ Lj for all i ≠ j.
• 1 ≤ Ai < Bi ≤ V, for all i.
• (Ai, Bi) ≠ (Aj, Bj) for all i ≠ j.
• 모든 마을이 두 종류의 식품을 모두 얻을 수 있는 계획이 적어도 하나 존재한다.

예제 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인 도로로 연결되어 있더라도 서로 다른 마을로 간주한다.