#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define maxn 5010
int T;
int n,m;
int cnt;
double mid;
int head[maxn];
int vis[maxn];
int sum[maxn];
double dis[maxn];
struct node
{
	int to;
	int nxt;
	double val;
}num[maxn];
void add(int u,int v,double w)
{
	num[++cnt].to=v;
	num[cnt].val=w;
	num[cnt].nxt=head[u];
	head[u]=cnt;
}
bool SPFA(int k)
{
	queue<int> qu;
	memset(dis,0x7f,sizeof(dis));
	memset(sum,0,sizeof(sum));
	memset(vis,0,sizeof(vis));
	dis[k]=0;
	vis[k]=1;
	qu.push(k); 
	while(!qu.empty())
	{
		int u=qu.front();
		qu.pop();
		vis[u]=0;
		for(int i=head[u];i;i=num[i].nxt)
		{
			int v=num[i].to;
			if(dis[v]>dis[u]+num[i].val-mid)
			{
				dis[v]=dis[u]+num[i].val-mid;
				if(!vis[v])
				{
					sum[v]++;
					if(sum[v]>=n)
					{
						return 1;	
					}
					vis[v]=1;
					qu.push(v);
				}
			}
		}
	}
	return 0;
}
int main()
{
//	freopen("UVA11090.out","w",stdout);
	scanf("%d",&T);
	for(int k=1;k<=T;k++)
	{
		cnt=0;
		memset(head,0,sizeof(head));
		double l=0,r=1e8,ma=1e8;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
		{
			int x,y;
			double w;
			scanf("%d%d%lf",&x,&y,&w);
			add(x,y,w);
		}
		while(l+1e-6<r)
		{
			mid=(l+r)/2.0;
			int flag=0;
			for(int i=1;i<=n;i++)
			{
				if(SPFA(i)) flag=1;
				break;
			}
			if(flag)
			{
				r=mid;
			}
			else
			{
				l=mid;
			}
		}
		if(k==T)
		{
			if(r==ma)
			{
				printf("Case #%d: No cycle found.",k);
				continue; 
			}
			printf("Case #%d: %.2lf",k,r);
		}
		else 
		{
			if(r==ma)
			{
				printf("Case #%d: No cycle found.\n",k);
				continue; 
			}
			printf("Case #%d: %.2lf\n",k,r);
		}
	}
	return 0;
}