#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <functional>
#include <limits>
#include <queue>
#include <iomanip>
#include <deque>
#include <stack>
#include <cstdio>
#include <cmath>
#include <complex.h>
#include <cstdio>

using namespace std;

long long dist[1001][1001];
long long cost[1001][1001];

vector<int> g[1001];

void dfs(int v, int p, int f, long long c)
{
    dist[f][v] = dist[v][f] = c;

    for (int adj_v : g[v])
        if (adj_v != p)
            dfs(adj_v, v, f, c + cost[v][adj_v]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T;
    cin >> T;

    for (int test_case = 1; test_case <= T; test_case++)
    {
        int n, k;
        cin >> n >> k;

        for (int v = 1; v <= n; v++)
            g[v].clear();

        for (int v = 2; v <= n; v++)
        {
            int parent, length;
            cin >> parent >> length;

            cost[parent][v] = cost[v][parent] = length;
            g[v].push_back(parent);
            g[parent].push_back(v);
        }

        for (int v = 1; v <= n; v++)
            dfs(v, v, v, 0);

        int max_v = 2;
        for (int v = 3; v <= n; v++)
            if (dist[1][v] > dist[1][max_v])
                max_v = v;

        bool used[1001] = {};
        int next[1001] = {};

        next[1] = max_v;
        next[max_v] = 1;
        used[max_v] = true;

        long long max_path_length = 2 * dist[1][max_v];

        for (int i = 2; i <= k; i++)
        {
            int best_v = -1;
            int best_place = -1;
            long long best_increase = -1;

            for (int v = 2; v <= n; v++)
                if (!used[v])
                {
                    int v0 = 1;
                    int v1 = next[v0];
                    do
                    {
                        long long cur_dist = dist[v0][v1];
                        long long new_dist = dist[v0][v] + dist[v][v1];
                        long long increase = new_dist - cur_dist;

                        if (increase > best_increase)
                        {
                            best_increase = increase;
                            best_v = v;
                            best_place = v0;
                        }

                        v0 = v1;
                        v1 = next[v0];

                    } while (v0 != 1);
                }

            used[best_v] = true;

            int tmp = next[best_place];
            next[best_place] = best_v;
            next[best_v] = tmp;

            max_path_length += best_increase;
        }

        cout << "Case #" << test_case << ": " << max_path_length;
        if (test_case < T)
            cout << '\n';
    }
}