#include <iostream>
#include <vector>
#include <algorithm>
 
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()
{
    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';
    }
}