#include<bits/stdc++.h>
using namespace std;
int T,n,m;
class graph{
private:
	struct edge{
		int u,v,next;
		double w;
	};
	edge e[100001];
	int head[101],cnt;
	double dis[101];
	bool inque[101];
public:
	graph()
	{
        memset(head,0,sizeof(head));
		cnt=0;
	}
	void add(int u, int v, double w)
	{
		e[++cnt]=(edge){u,v,head[u],w};
		head[u]=cnt;
	}
	void edit(double w)
	{
		for(int i=1; i<=cnt; i++) e[i].w+=w;
	}
	bool spfa(int u,double x)
	{
		inque[u]=1;
		int v;
		for(int i=head[u]; i; i=e[i].next)
		{
            v=e[i].v;  
			if(dis[u]+e[i].w-x<dis[v])
			{
                    
				dis[v]=dis[u]+e[i].w-x;
				if(inque[v] || spfa(v,x)) return 1;
			}
		}
		inque[u]=0;
		return 0;
	}
	bool getNCycle(double x)
	{
		fill(dis+1,dis+1+n,1e10);
		memset(inque,0,sizeof(inque));
		for(int i=1; i<=n; i++)
		{
			if(spfa(i,x))
				return 1;
		}
		return 0;
	}
};
int main()
{

	cin>>T;
	int tmp=T;
	while(T--)
	{
		graph x;
		cin>>n>>m;
		double low=0x7fffffff,high=0,ans=-1;
		for(int i=1; i<=m; i++)
		{
			int u,v;
			double w;
			scanf("%d %d %lf",&u,&v,&w);
			x.add(u,v,w);
			low=min(low,w);
			high=max(high,w);
		}
		while(high-low>=1e-8)
		{
			double mid=(low+high)/2;
            //cout<<mid<<endl;
			if(x.getNCycle(mid))
			{
				ans=mid;
				high=mid;
			}
			else low=mid;
		}
		printf("Case #%d: ",tmp-T);
		if(ans==-1) cout<<"No cycle found.\n";
		else printf("%.2lf\n",ans); 
	}
	return 0;
}