#include <iostream>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <bitset>
#include <functional>
#include <numeric>
#include <utility>
#include <iomanip>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <deque>
#include <ctime>
#define SET(p) memset(p,-1,sizeof(p))
#define CLR(p) memset(p,0,sizeof(p))
#define LL long long int
#define ULL unsigned long long int
#define pb push_back
#define cin(n) scanf("%d",&n)
using namespace std;
#define mp make_pair
#define ill long long

struct node
{
    int x,y,cost;
    double cc;
    node(int a,int b,int c)
    {
        x=a,y=b,cost=c;
        cc=c*1.0;
    }
};

bool comp(node a,node b)
{
    return a.cost<b.cost;
}
int m,n;
vector<node>edge;
double min(double a,double b)
{
    return a<b?a:b;
}
bool bellman(double mid)
{
    int i,j;

    double dis[n+9];
    for(i=0;i<=n;i++)
        dis[i]=100000000000.0;
dis[1]=0.0;
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
        {
            int u=edge[j].x;
            int v=edge[j].y;
            dis[v]=min(dis[v],dis[u]+edge[j].cc-mid);
        }
    }

    for(i=0;i<m;i++)
    {
        int u=edge[i].x;
        int v=edge[i].y;
        if(dis[v]>(dis[u]+edge[i].cc-mid))
            return 1;
    }

return 0;

}
int main()
{
    int t,i,j,k,l;

    cin(t);
    int ct=1;
    while(t--)
    {
        cin(n);
        cin(m);


        edge.clear();
        double sum=0.0;
        for(i=0;i<m;i++)
        {
            cin(j);cin(k);
            cin(l);
            edge.pb(node(j,k,l));
            sum+=l*1.0;
        }

        sort(edge.begin(),edge.end(),comp);

        double low,high;

        low=0.0;
        high=sum;
        double ans=-1.0;
        while((high-low)>1e-3)
        {
            double mid=(low+high)/2.0;

            if(bellman(mid))
            {
                ans=mid;
                high=mid-1e-3;
            }
            else
                low=mid+1e-3;
        }
        cout<<"Case #"<<ct++<<": ";
        if(ans==-1.0)
            cout<<"No cycle found\n";
        else
            printf("%.2lf\n",ans);

    }
    return 0;
}