#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define eb emplace_back
#define INF 10000010
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a, max(b,c))
using namespace std;

int N, visitado[70];

struct edge{
  int src,dest,w;
  edge(int a, int b, int c): src(a), dest(b), w(c){}
};


bool bellman(vector<edge> &arestas, double x)
{
  int tam = arestas.size();
  double d[N+10];
  FOR(i, 0, N+5)d[i] = 0*1.0;
  FOR(i,1,N)
    FOR(j, 0,tam)
    {
      int source = arestas[j].src;
      int destiny = arestas[j].dest;
      double weight = arestas[j].w*1.0;
      if (d[destiny]>d[source]+weight - x){
        d[destiny] = d[source]+weight -x;
      }

    }
  FOR(j,0,tam)
  {
    int source = arestas[j].src;
      int destiny = arestas[j].dest;
      double weight = arestas[j].w*1.0;
      if (d[destiny]>d[source]+weight - x)
        return 1;
  }
  return 0;
}

int main()
{
  ios_base::sync_with_stdio(false);cin.tie(NULL);
  int t,kk=0;
  cin>>t;
  while (kk<t)
  {
    kk++;
    cout<<"Case #"<<kk<<": ";
    int M,menor=INF,maior=INF;
    cin>>N>>M;
    vector<edge> arestas;
    FOR(i, 0, M)
    {
      int a,b,c;
      cin>>a>>b>>c;
      arestas.eb(a,b,c);
      if(maior==INF) maior = c;
      else maior=max(c,maior);
      menor = min(menor,c);
    }
    double fim = maior*1.0,ini = menor*1.0,best=INF*1.0;
    while (fim - ini>0.001)
    {
      double mid = (fim+ini)/2.0;
      if (bellman(arestas, mid)) best=fim = mid;
      else ini = mid;
    }
    if (best==INF)
    {
      cout<<"No cycle found."<<endl;
      continue;
    }
    cout.precision(2);
  cout.setf(ios::fixed);
    cout<<ini<<endl;
  }
}