#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn =  + ;

struct node {

    int u, v, w, tonext;

    bool flag;

} e[maxn * ];

int first[maxn];

int num;

int in[maxn];

int DFN;

void add(int u, int v, int w, bool flag) {

    ++num;

    e[num].u = u;

    e[num].v = v;

    e[num].w = w;

    e[num].tonext = first[u];

    first[u] = num;

    e[num].flag = flag;

}

int now;

int dfs(int cur, int root, int fa) {

    if (cur == root && now == ) return ;

    if (cur == root) {

        for (int i = first[cur]; i; i = e[i].tonext) {

            now--;

            if (now == ) {

                return e[i].w + dfs(e[i].v, root, cur);

            }

        }

    } else {

        for (int i = first[cur]; i; i = e[i].tonext) {

            int v = e[i].v;

            if (v == fa) continue;

            if (e[i].flag) {

                return dfs(v, root, cur);

            } else {

                return e[i].w + dfs(v, root, cur);

            }

        }

    }

}

void work() {

    num = ;

    ++DFN;

    int n;

    scanf("%d", &n);

    int root = -inf;

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

        int u, v, w;

        scanf("%d%d%d", &u, &v, &w);

        if (in[v] == DFN) {

            root = v;

        }

        in[v] = DFN;

        add(u, v, w, true);

        add(v, u, w, false);

    }

    int ans = inf;

    if (root == -inf) {

        ans = ;

    } else {

        now = ;

        ans = dfs(root, root, );

        now = ;

        ans = min(ans, dfs(root, root, ));

    }

    static int f = ;

    printf("Case %d: %d\n", ++f, ans);

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}