/**
 * FWP, AusgewÀhlte Probleme aus dem ACM Programming Contest 
 * Problem:     11090 - Going in Cycle!!
 * Link:        http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=22&page=show_problem&problem=2031
 * 
 *
 * Method :     floyd warshall + binary search
 * Status :     Accepted
 * Runtime:     1.480
 *
 * @author      Evgeni Pavlidis 
 * @version     1.0, 27/10/2010
 */


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

class Main 
{
    static long MAX = 10000000;
    static int n,m;

    // do floyd-warshall on graph with subtracting M from all weights
    // return the min cycle found (Double.MAX_VALUE if no such)
    static double floydWarshall(double[][] aG, double M)
    {	   
	double[][] g = new double[50][50];

	for(int i = 0; i < n; i++)
	    for(int j = 0; j < n; j++)
		g[i][j] = aG[i][j] - M;

	for(int k = 0; k < n; k++)
	    for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
		    if(k != i && k != j)	
			g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
	    
	    
	double min = Double.MAX_VALUE;
	for(int i = 0; i < n; i++)
	    if(g[i][i] < min)
		min = g[i][i];
	    
	return min;
    }

    public static void main(String...args)
    {
	double[][] g = new double[50][50];

	Scanner sc = new Scanner(System.in);
	long c;
	int a,b;

	int testCases = sc.nextInt();	
	for(int tc = 1; tc <= testCases; tc++)
	{
	    n = sc.nextInt();
	    m = sc.nextInt();

	    // init
	    for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
		    g[i][j] = Double.POSITIVE_INFINITY;

	    // read input
	    for(int i = 0; i < m; i++)
	    {
		a = sc.nextInt()-1;
		b = sc.nextInt()-1;
		c = sc.nextLong();
		g[a][b] = Math.min(g[a][b], c);

	    }
	    
	    // binary search for the mean
	    double test = Double.MAX_VALUE;
	    double l = 0, m = 0, h = MAX;

	    int count = 0;
	    while(Math.abs(test) > 0.001 && (count++ < MAX))
	    {
		m = (h+l)/2.0;
		test = floydWarshall(g, m);

		if(test == Double.MAX_VALUE)
		    break;

		if(test < 0)
		    h = m;		    
		else
		    l = m;
	    }


	    if(test == Double.MAX_VALUE)
		System.out.printf("Case #%d: No cycle found.\n", tc);
	    else
		System.out.printf("Case #%d: %.2f\n", tc, m);		
	}

    }
}