import java.util.*;
import java.io.*;

public class Solution {
	public static void main(String[] args) {
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int t = in.nextInt();
		for (int i = 1; i <= t; ++i) {
			int n = in.nextInt();
			int m = in.nextInt();
			int p = in.nextInt();
			int[][] d = new int[n][n];
			for (int j = 0; j < n; ++j) {
				for (int k = 0; k < n; ++k) {
					d[j][k] = Integer.MAX_VALUE / n;
				}
			}
			for (int j = 0; j < m; ++j) {
				int u = in.nextInt();
				int v = in.nextInt();
				int di = in.nextInt();
				d[u - 1][v - 1] = di;
				d[v - 1][u - 1] = di;
			}
			for (int j = 0; j < n; ++j) {
				for (int k = 0; k < n; ++k) {
					for (int l = 0; l < n; ++l) {
						d[k][l] = Math.min(d[k][l], d[k][j] + d[j][l]);
					}
				}
			}
			double[][] dp = new double[p + 1][n];
			for (int j = 1; j <= p; ++j) {
				for (int k = 0; k < n; ++k) {
					for (int l = 0; l < n; ++l) {
						if (k != l) {
							dp[j][k] += (dp[j - 1][l] + d[l][k]) / (n - 1);
						}
					}
				}
			}
			System.out.println("Case #" + i + ": " + dp[p][0]);
		}
		in.close();
	}
}