모두 잡아라

Codejamon Go이 출시된 후, 당신은 많은 친구들처럼 털이 복슬복슬한 작은 생명체를 최대한 많이 잡기 위해 도시의 거리로 나섰다. 이 게임의 목표는 도시 곳곳에 나타나는 Codejamon의 위치로 이동하여 그들을 잡는 것이다. 당신은 그들을 모두 잡는 데 얼마나 오래 걸릴지 궁금하다!

당신의 도시는 1부터 N까지 번호가 매겨진 N개의 장소로 이루어져 있다. 당신은 장소 1에서 시작한다. M개의 양방향 도로가 있으며, 도로에는 1부터 M까지 번호가 매겨져 있다. i번째 도로는 서로 다른 한 쌍의 장소 ($U_{i}$, $V_{i}$)를 연결하며, 어느 방향으로든 이 도로를 이동하는 데 $D_{i}$분이 걸린다. 하나 이상의 도로를 따라 이동하면 장소 1에서 다른 어떤 장소로도 도달할 수 있음이 보장된다.

시각 0에 Codejamon 하나가 현재 위치 이외의 장소 중 균등하게 무작위인 한 장소에 나타난다. 시각 0에서 현재 위치는 장소 1이다. 균등하게 무작위라는 것은 현재 위치 이외의 N - 1개 장소 각각에 나타날 확률이 정확히 1 / (N - 1)이라는 뜻이다. Codejamon이 나타나는 즉시 그쪽으로 이동하기 시작할 수 있다. Codejamon이 있는 장소에 도착하면 즉시 그것을 잡으며, 그러면 새로운 Codejamon 하나가 현재 위치 이외의 장소 중 균등하게 무작위인 한 장소에 즉시 나타나고, 이 과정이 계속된다. 어느 시점에든 존재하는 Codejamon은 단 하나뿐이며, 다음 Codejamon이 나타나기 전에 기존 Codejamon을 잡아야 한다는 점에 유의하라.

도시의 배치가 주어질 때, 어떤 두 장소 사이를 이동할 때도 항상 가능한 가장 빠른 경로를 택한다고 가정하고 P Codejamon을 잡는 데 걸리는 기댓값을 계산하라.

제한

1 ≤ T ≤ 100. 테스트 세트당 시간 제한: 40초. 메모리 제한: 1GB. N - 1 ≤ M ≤ (N * (N - 1)) / 2. 모든 i에 대해, 1 ≤ $D_{i}$ ≤ 10. 모든 i에 대해, 1 ≤ $U_{i}$ < $V_{i}$ ≤ N. i ≠ j인 모든 i와 j에 대해, $U_{i}$ ≠ $U_{j}$ 및/또는 $V_{i}$ ≠ $V_{j}$. (어떤 두 장소 사이에도 도로는 최대 하나만 존재한다.) 하나 이상의 도로를 따라 이동하면 장소 1에서 다른 어떤 장소로도 도달할 수 있음이 보장된다.

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

2 ≤ N ≤ 50. 1 ≤ P ≤ 200.

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

2 ≤ N ≤ 100. 1 ≤ P ≤ $10^{9}$.

입력은 테스트 케이스의 수를 나타내는 정수 T 하나가 포함된 한 줄로 시작한다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 장소의 수, 도로의 수, 잡아야 하는 Codejamon의 수를 각각 나타내는 정수 N, M, P 3개가 포함된 한 줄로 시작한다.

그다음 각 테스트 케이스에는 M개의 줄이 이어진다. 이 중 i번째 줄에는 세 정수 $U_{i}$, $V_{i}$, $D_{i}$가 포함되며, 이는 i번째 도로가 장소 $U_{i}$와 $V_{i}$ 사이에 있고 어느 방향으로든 이 도로를 이동하는 데 $D_{i}$분이 걸린다는 뜻이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y은 P Codejamon을 잡는 데 걸리는 시간의 기댓값을 분 단위로 나타낸 것이다. 답이 정답과의 절대 오차 또는 상대 오차가 10^{-4} 이내이면 정답으로 인정된다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 관한 설명은 FAQ을 참조하라.

예제 케이스 #1에서는 잡아야 하는 Codejamon이 하나뿐이다. 이 Codejamon은 같은 확률로 장소 2, 3, 4, 5 중 하나에 나타나며, 이 장소들은 시작 위치 1에서 각각 1, 3, 2, 3만큼 떨어져 있다. 따라서 걸리는 시간의 기댓값은 (1 + 3 + 2 + 3) / 4 = 2.25분이다.

예제 케이스 #2에서는 하나의 도로로 연결된 장소가 두 곳뿐이다. Codejamon이 나타날 때마다 현재 위치가 아닌 다른 장소에 나타나므로, 그곳에 가려면 도로를 이용해야 한다. 따라서 도로를 200번 이용하고 매번 5분이 걸리므로, 총 1000분이 걸린다.

예제 케이스 #3은 예제 케이스 #1와 같은 지도를 사용한다. 두 Codejamon이 나타날 장소에 대해 16개의 순서쌍 가능성이 있으며, 계산하면 기댓값은 87/16 = 5.4375분이다.

예제 케이스 #4에서 잡아야 하는 Codejamon 하나는 장소 2 또는 장소 3에 나타난다. 장소 2에 나타난다면 시간이 더 오래 걸리는 1에서 2로 가는 도로를 이용하는 것보다, 1에서 3로 가는 도로와 3에서 2로 가는 도로를 거쳐 이 분 만에 도착하는 편이 낫다. 따라서 걸리는 시간의 기댓값은 (2 + 1) / 2 = 1.5분이다.