One Way Roads

#include<bits/stdc++.h>
using namespace std;
typedef long long  ll;
typedef unsigned long long ull;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL))
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fi first
#define se second
#define pb push_back
const int mod = 1e9+7;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL))
const int N=1e6;
#define eb emplace_back
//int X[] = {-1,0,1,1,1,0,-1,-1};
//int Y[] = {-1,-1,-1,0,1,1,1,0};
int X[] = {-1,1,0,0};
int Y[] = {0,0,-1,1};
bool iset(ll n, ll k)
{
    if (n & (1ll << k))return true;
    else return false;
}

vector<pll>adj[N+10];
ll n;
bool vis[N+10];
ll cost[N+1];
ll way=0;
void dfs(ll s){
    vis[s]=true;
    for(auto x:adj[s]){
            ll node=x.fi;
            ll w=x.se;
        if(!vis[node]){
            way+=w;
            dfs(node);
        }
    }
}
int main()
{
     fastread();
     ll t,cs=0;
     cin>>t;
     while(t--){
        cin>>n;
       map<pll,ll>mp;
        for(ll i=1;i<=n;i++){
            ll a,b,w;
            cin>>a>>b>>w;
       adj[a].pb({b,0});
         //    mp[{a,b}]=0;
            adj[b].pb({a,w});
         if(a==1) mp[{b,a}]=w;
        }

        vis[1]=true;
        ll way1=adj[1][0].se;
        way=0;
        dfs(adj[1][0].fi);
      //  cout<<"way "<<way<<endl;
        way1+=way+mp[{adj[1][1].fi,1}];
        for(ll i=0;i<=n;i++){
            vis[i]=false;
        }

        vis[1]=true;
        ll way2=adj[1][1].se;
        way=0;
        dfs(adj[1][1].fi);
       // cout<<"way "<<way<<endl;
        way2+=way+mp[{adj[1][0].fi,1}];
      //  cout<<adj[1][0].fi<<" - "<<way1<<"\n  "<<adj[1][1].fi<<" -> "<<way2<<endl;
        cout<<"Case "<<++cs<<": ";
        cout<<min(way1,way2)<<endl;

        for(ll i=0;i<=n;i++){
            adj[i].clear();
            vis[i]=false;
        }

     }

}