#include<iostream>

#include<vector>

#include<cstring>

#include<string>

#include<queue>

#include<algorithm>

#include<iomanip>

#include<cstdio>

#define MAX_N 66

#define INF 50000000000

#define eps 1e-4

using namespace std;

typedef long long ll;

int T;

int n,m;

struct edge {

public:

    int to;

    double cost;

    edge(int t, double c) : cost(c), to(t) { }

    edge() { }

};

vector<edge> G[MAX_N];

int cas = ;

queue<int> que;

bool inQue[MAX_N];

double d[MAX_N];

int cnt[MAX_N];

bool vis[MAX_N];

bool spfa(int s) {

    fill(d, d + n + , INF);

    while (que.size())que.pop();

    memset(inQue, , sizeof(inQue));

    que.push(s);

    inQue[s] = ;

    d[s] = ;

    memset(cnt, , sizeof(cnt));

    cnt[s]++;

    while (que.size()) {

        int u = que.front();

        vis[u]=;

        que.pop();

        inQue[u] = ;

        for (int i = ; i < G[u].size(); i++) {

            int v = G[u][i].to;

            double t = G[u][i].cost + d[u];

            if (t < d[v]) {

                d[v]=t;

                if(!inQue[v]) {

                    que.push(v);

                    inQue[v] = ;

                    cnt[v]++;

                    if (cnt[v] > n)return true;

                }

            }

        }

    }

    return false;

}

bool check(double mid) {

    for (int i = ; i <= n; i++)

        for (int j = ; j < G[i].size(); j++)

            G[i][j].cost -= mid;

    bool flag;

    memset(vis, , sizeof(vis));

    for (int i = ; i <= n; i++) {

        if (!vis[i]) {

            flag = spfa(i);

            if(flag)break;

        }

    }

    for (int i = ; i <= n; i++)

        for (int j = ; j < G[i].size(); j++)

            G[i][j].cost += mid;

    return flag;

}

int main() {

    cin.sync_with_stdio(false);

    cin >> T;

    while (T--) {

        cin >> n >> m;

        for (int i = ; i <= n; i++)G[i].clear();

        int u, v;

        double c;

        for (int i = ; i < m; i++) {

            cin >> u >> v >> c;

            G[u].push_back(edge(v, c));

        }

        double l = , r = ;

        while (l + eps < r) {

            double mid = (l + r) / ;

            if (check(mid))r = mid;

            else l = mid;

        }

        if (!(fabs(r-)<eps))

            cout << "Case #" << ++cas << ": " << setprecision() << fixed << l << endl;

        else

            cout << "Case #" << ++cas << ": No cycle found." << endl;

    }

    return ;

}