#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
int T;
int n,m,cnt[55];
double d[55];
struct road
{
	int v;
	double w;	
};
vector<road>ro[55];
bool v[55];
queue<int>q;
int main()
{
	scanf("%d",&T);
	int t=T;
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)ro[i].clear();
		for(int i=1;i<=m;i++)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			ro[a].push_back({b,(double)(c)});
		}
		double r=10000000,l=0;
		while(fabs(r-l)>=1e-3)
		{
			double mid=(l+r)/2.0;
			for(int i=1;i<=n;i++)
			{
				for(int j=0;j<(int)(ro[i].size());j++)
				{
					ro[i][j].w-=mid;
				}
			}
			for(int i=1;i<=n;i++)d[i]=0x3f3f3f3f;
			memset(v,false,sizeof(v));
			memset(cnt,0,sizeof(cnt));
			q.push(1);
			d[1]=0;
			v[1]=true;
			bool flag=false;
			while(!q.empty())
			{
				int x=q.front();
				q.pop();
				v[x]=false;
				for(int i=0;i<(int)(ro[x].size());i++)
				{
					if(d[ro[x][i].v]>d[x]+ro[x][i].w)
					{
						d[ro[x][i].v]=d[x]+ro[x][i].w;
						cnt[ro[x][i].v]=cnt[x]+1;
						if(cnt[ro[x][i].v]>=n)
						{
							flag=true;
							break;
						}
						if(!v[ro[x][i].v])
						{
							q.push(ro[x][i].v);
							v[ro[x][i].v]=true;
						}
					}
				}
				if(flag)break;
			}
			if(flag)r=mid;
			else l=mid;
			for(int i=1;i<=n;i++)
			{
				for(int j=0;j<(int)(ro[i].size());j++)
				{
					ro[i][j].w+=mid;
				}
			}		
		}
		printf("Case #%d: ",t-T);
		if(fabs(l-10000000.0)<=1e-3)printf("No cycle found.\n");
		else printf("%.2lf\n",l);		
	}
	return 0;
}

提交记录