// Arup Guha
// 3/12/2018
// Solution to 2018 UCF HS Contest Problem: Lazy Bob

import java.util.*;

public class lazy {

	public static int n;
	public static int e;
	public static int newR;
	public static ArrayList<Integer> possible;
	public static ArrayList[] g;
	public static edge[] eList;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();

		// Process each case.
		for (int loop=1; loop<=nC; loop++) {

			// Read in the graph.
			n = stdin.nextInt();
			newR = stdin.nextInt();
			e = stdin.nextInt();
			eList = new edge[e];
			g = new ArrayList[n];
			for (int i=0; i<n; i++) g[i] = new ArrayList<edge>();

			// Now get the edges.
			for (int i=0; i<e; i++) {
				int u = stdin.nextInt()-1;
				int v = stdin.nextInt()-1;
				int w = stdin.nextInt();
				eList[i] = new edge(u, v, w, i);
				g[u].add(eList[i]);
			}

			// Fill with all path lengths.
			possible = new ArrayList<Integer>();
			wrapper();

			// Sum each factor.
			double sum = 1;
			for (Integer x : possible)
				sum += (1.0*newR/x);

			// Convert to desired percentage.
			double flip = 100.0/sum;

			// Output.
			System.out.printf("City #%d: %.3f", loop, flip);
			System.out.println("%");
		}

	}

	// Get recursion started.
	public static void wrapper() {
		go(0, 0, new boolean[e]);
	}

	public static void go(int curV, int curW, boolean[] used) {

		// Got to the end.
		if (curV == n-1) {
			possible.add(curW);
			return;
		}

		// Try each edge as the next edge.
		for (int i=0; i<used.length; i++) {

			// Used this edge.
			if (used[i]) continue;

			// This road doesn't start where we are.
			if (eList[i].u != curV) continue;

			// Mark it and go.
			used[i] = true;
			go(eList[i].v, curW+eList[i].w, used);
			used[i] = false;
		}
	}
}

class edge {

	public int u;
	public int v;
	public int w;
	public int id;

	public edge(int from, int to, int myw, int myid) {
		u = from;
		v = to;
		w = myw;
		id = myid;
	}
}