/**

题目：hdu6005 Pandaland

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6005

题意：给定一个带权无向图，求权值和最小的环的值，如果不存在环输出0；

思路：枚举每条边，然后dijkstra求s到t的距离，dijkstra过程中舍去s-t的这条边。

两个优化：dijkstra找到了t就跳出。或者出队列的距离>=当前找到的最小距离跳出。

*/

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<vector>

#include<queue>

#include<cstring>

using namespace std;

typedef pair<int,int> P;

typedef long long LL;

const int N = 4e3+;

const int INF = 0x3f3f3f3f;

struct edge{int to, cost;};

int V, mis;

vector<edge> G[*N];

int d[N*+];

void dijkstra(int s,int t)

{

    priority_queue<P,vector<P>, greater<P> > que;

    fill(d,d+V,INF);

    d[s] = ;

    que.push(P(,s));

    while(!que.empty()){

        P p = que.top(); que.pop();

        int v = p.second;

        if(d[v]<p.first) continue;

        if(v==t) break;

        if(d[v]>=mis) break;

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

            edge e = G[v][i];

            if(v==s&&e.to==t) continue;

            if(d[e.to]>d[v]+e.cost){

                d[e.to] = d[v]+e.cost;

                que.push(P(d[e.to],e.to));

            }

        }

    }

}

map<P,int> mp;

struct node

{

    int u,v;

    int cost;

}Eg[N];

int main()

{

    int cas = , T, m;

    cin>>T;

    while(T--)

    {

        int cnt = ;

        scanf("%d",&m);

        int cost, x1, y1, x2, y2;

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

        mp.clear();

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

            scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&cost);

            int u, v;

            if(mp[P(x1,y1)]==){

                mp[P(x1,y1)] = cnt++;

            }

            if(mp[P(x2,y2)]==){

                mp[P(x2,y2)] = cnt++;

            }

            u = mp[P(x1,y1)], v = mp[P(x2,y2)];

            G[u].push_back(edge{v,cost});

            G[v].push_back(edge{u,cost});

            Eg[i].cost = cost;

            Eg[i].u = u;

            Eg[i].v = v;

        }

        mis = INF;

        V = cnt;

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

            dijkstra(Eg[i].u,Eg[i].v);

            mis = min(mis,d[Eg[i].v]+Eg[i].cost);

        }

        if(mis==INF){

            printf("Case #%d: 0\n",cas++);

        }else

        printf("Case #%d: %d\n",cas++,mis);

    }

    return ;

}