모두 잡아라

Codejamon Go가 출시된 뒤, 당신은 친구들처럼 도시 거리로 나가 귀여운 생물들을 최대한 많이 잡았다. 이 게임의 목표는 도시 곳곳에 나타나는 Codejamon의 위치로 이동해 잡는 것이다. 당신은 그것들을 모두 잡는 데 얼마나 걸릴지 궁금해졌다.

도시는 1번부터 N번까지 번호가 붙은 N개의 장소로 이루어져 있다. 당신은 1번 장소에서 시작한다. M개의 양방향 도로가 있으며 1번부터 M번까지 번호가 붙어 있다. i번째 도로는 서로 다른 두 장소 (Ui, Vi)를 연결하고, 어느 방향으로 가든 Di분이 걸린다. 1번 장소에서 하나 이상의 도로를 따라 이동하면 다른 모든 장소에 도달할 수 있다.

시각 0에 Codejamon 하나가 당신의 현재 위치(시각 0에는 1번 장소)가 아닌 곳에 균일한 확률로 나타난다. 균일한 확률이란 현재 위치가 아닌 나머지 N - 1개 장소 각각에 나타날 확률이 정확히 1 / (N - 1)이라는 뜻이다. Codejamon이 나타나는 순간 당신은 즉시 그것을 향해 이동을 시작할 수 있다. Codejamon이 있는 장소에 도착하면 즉시 잡고, 그러면 새로운 Codejamon이 당신의 현재 위치가 아닌 곳에 균일한 확률로 즉시 나타나며, 이 과정이 반복된다. 어느 시각에도 Codejamon은 하나만 존재하며, 다음 Codejamon이 나타나기 전에 현재 있는 Codejamon을 잡아야 한다.

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

입력은 첫 줄에 정수 T 하나로 시작한다. 이는 테스트 케이스의 수이다. T개의 테스트 케이스가 이어진다.

각 테스트 케이스는 N, M, P 세 정수가 있는 한 줄로 시작한다. 각각 장소의 수, 도로의 수, 잡아야 할 Codejamon의 수이다.

그다음 각 테스트 케이스에는 M개의 줄이 이어진다. 이 중 i번째 줄에는 세 정수 Ui, Vi, Di가 있다. i번째 도로가 장소 Ui와 Vi를 연결하며 어느 방향으로 가든 Di분이 걸린다는 뜻이다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, y는 P마리의 Codejamon을 잡는 데 걸리는 기대 시간(분)이다. 답이 정답과 절대 오차 또는 상대 오차로 10-4 이내이면 정답으로 인정된다.

• 1 ≤ T ≤ 100.
• N - 1 ≤ M ≤ (N * (N - 1)) / 2.
• 모든 i에 대해 1 ≤ Di ≤ 10.
• 모든 i에 대해 1 ≤ Ui < Vi ≤ N.
• i ≠ j인 모든 i, j에 대해 Ui ≠ Uj이거나 Vi ≠ Vj이다. (두 장소 사이에는 도로가 최대 하나 있다.)
• 1번 장소에서 하나 이상의 도로를 따라 이동하면 다른 모든 장소에 도달할 수 있다.

예제 1에서는 잡아야 할 Codejamon이 하나뿐이다. 같은 확률로 장소 2, 3, 4, 5에 나타나며, 시작 위치 1에서 각각 1, 3, 2, 3분 거리에 있다. 따라서 걸리는 기대 시간은 (1 + 3 + 2 + 3) / 4 = 2.25분이다.

예제 2에서는 도로 하나로 연결된 장소가 둘뿐이다. Codejamon이 나타날 때마다 현재 위치가 아닌 다른 장소에 나타나고, 우리는 도로를 따라 거기로 가야 한다. 따라서 5분씩 걸리는 도로를 200번 지나 총 1000분이 걸린다.

예제 3은 예제 1과 같은 지도를 사용한다. 두 Codejamon이 나타날 위치의 순서쌍은 16가지이고, 계산하면 기대 시간은 87/16 = 5.4375분이다.

예제 4에서 잡아야 할 Codejamon 하나는 장소 2 또는 장소 3에 나타난다. 장소 2에 나타나면 시간이 더 걸리는 1번에서 2번으로 가는 도로 대신 1번에서 3번, 3번에서 2번으로 가는 도로를 이용해 2분 만에 가는 편이 낫다. 따라서 걸리는 기대 시간은 (2 + 1) / 2 = 1.5분이다.