#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int n,cnt[N];
double dis[N];
bool vis[N];
struct node{
	int x;
	double w;
};
vector<node>nbr[N];
bool spfa(double X){
	queue<int> q;
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=n;i++){
		dis[i]=0;
		q.push(i);
		vis[i]=true;
	}
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=false;
		for(int i=0;i<nbr[x].size();i++){
			int y=nbr[x][i].x;
			double w=nbr[x][i].w-X;
			if(dis[x]+w<dis[y]){
				dis[y]=dis[x]+w;
				cnt[y]=cnt[x]+1;
				if(cnt[y]>=n) return true;
				if(vis[y]==false){
					vis[y]=true;
					q.push(y);
				}
			}
		}
	}
	return false;
}
int main(){
	int T,m;
	cin>>T;
	for(int t=1;t<=T;t++){
		double l=1e9,r=-1e9;
		cin>>n>>m;
		for(int i=1;i<=m;i++){
			int x,y;
			double w;
			cin>>x>>y>>w;
			nbr[x].push_back((node){y,w});
			l=min(l,w);r=max(r,w);
		}
		l--,r++;
		double tmp=r;
		while(l+1e-6<r){//eps=1e-6
			double mid=(l+r)/2;
			if(spfa(mid)) r=mid;
			else l=mid;
		}
		if(tmp==r) cout<<"Case #"<<t<<": No cycle found.";
		else cout<<"Case #"<<t<<": "<<fixed<<setprecision(2)<<r;
		cout<<endl;
	} 
}