#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';
}
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgogCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKbG9uZyBsb25nIGRpc3RbMTAwMV1bMTAwMV07CmxvbmcgbG9uZyBjb3N0WzEwMDFdWzEwMDFdOwogCnZlY3RvcjxpbnQ+IGdbMTAwMV07CiAKdm9pZCBkZnMoaW50IHYsIGludCBwLCBpbnQgZiwgbG9uZyBsb25nIGMpCnsKICAgIGRpc3RbZl1bdl0gPSBkaXN0W3ZdW2ZdID0gYzsKIAogICAgZm9yIChpbnQgYWRqX3YgOiBnW3ZdKQogICAgICAgIGlmIChhZGpfdiAhPSBwKQogICAgICAgICAgICBkZnMoYWRqX3YsIHYsIGYsIGMgKyBjb3N0W3ZdW2Fkal92XSk7Cn0KIAppbnQgbWFpbigpCnsKICAgIGludCBUOwogICAgY2luID4+IFQ7CiAKICAgIGZvciAoaW50IHRlc3RfY2FzZSA9IDE7IHRlc3RfY2FzZSA8PSBUOyB0ZXN0X2Nhc2UrKykKICAgIHsKICAgICAgICBpbnQgbiwgazsKICAgICAgICBjaW4gPj4gbiA+PiBrOwogCiAgICAgICAgZm9yIChpbnQgdiA9IDE7IHYgPD0gbjsgdisrKQogICAgICAgICAgICBnW3ZdLmNsZWFyKCk7CiAKICAgICAgICBmb3IgKGludCB2ID0gMjsgdiA8PSBuOyB2KyspCiAgICAgICAgewogICAgICAgICAgICBpbnQgcGFyZW50LCBsZW5ndGg7CiAgICAgICAgICAgIGNpbiA+PiBwYXJlbnQgPj4gbGVuZ3RoOwogCiAgICAgICAgICAgIGNvc3RbcGFyZW50XVt2XSA9IGNvc3Rbdl1bcGFyZW50XSA9IGxlbmd0aDsKICAgICAgICAgICAgZ1t2XS5wdXNoX2JhY2socGFyZW50KTsKICAgICAgICAgICAgZ1twYXJlbnRdLnB1c2hfYmFjayh2KTsKICAgICAgICB9CiAKICAgICAgICBmb3IgKGludCB2ID0gMTsgdiA8PSBuOyB2KyspCiAgICAgICAgICAgIGRmcyh2LCB2LCB2LCAwKTsKIAogICAgICAgIGludCBtYXhfdiA9IDI7CiAgICAgICAgZm9yIChpbnQgdiA9IDM7IHYgPD0gbjsgdisrKQogICAgICAgICAgICBpZiAoZGlzdFsxXVt2XSA+IGRpc3RbMV1bbWF4X3ZdKQogICAgICAgICAgICAgICAgbWF4X3YgPSB2OwogCiAgICAgICAgYm9vbCB1c2VkWzEwMDFdID0ge307CiAgICAgICAgaW50IG5leHRbMTAwMV0gPSB7fTsKIAogICAgICAgIG5leHRbMV0gPSBtYXhfdjsKICAgICAgICBuZXh0W21heF92XSA9IDE7CiAgICAgICAgdXNlZFttYXhfdl0gPSB0cnVlOwogCiAgICAgICAgbG9uZyBsb25nIG1heF9wYXRoX2xlbmd0aCA9IDIgKiBkaXN0WzFdW21heF92XTsKIAogICAgICAgIGZvciAoaW50IGkgPSAyOyBpIDw9IGs7IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGludCBiZXN0X3YgPSAtMTsKICAgICAgICAgICAgaW50IGJlc3RfcGxhY2UgPSAtMTsKICAgICAgICAgICAgbG9uZyBsb25nIGJlc3RfaW5jcmVhc2UgPSAtMTsKIAogICAgICAgICAgICBmb3IgKGludCB2ID0gMjsgdiA8PSBuOyB2KyspCiAgICAgICAgICAgICAgICBpZiAoIXVzZWRbdl0pCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaW50IHYwID0gMTsKICAgICAgICAgICAgICAgICAgICBpbnQgdjEgPSBuZXh0W3YwXTsKICAgICAgICAgICAgICAgICAgICBkbwogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgbG9uZyBsb25nIGN1cl9kaXN0ID0gZGlzdFt2MF1bdjFdOwogICAgICAgICAgICAgICAgICAgICAgICBsb25nIGxvbmcgbmV3X2Rpc3QgPSBkaXN0W3YwXVt2XSArIGRpc3Rbdl1bdjFdOwogICAgICAgICAgICAgICAgICAgICAgICBsb25nIGxvbmcgaW5jcmVhc2UgPSBuZXdfZGlzdCAtIGN1cl9kaXN0OwogCiAgICAgICAgICAgICAgICAgICAgICAgIGlmIChpbmNyZWFzZSA+IGJlc3RfaW5jcmVhc2UpCiAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJlc3RfaW5jcmVhc2UgPSBpbmNyZWFzZTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGJlc3RfdiA9IHY7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBiZXN0X3BsYWNlID0gdjA7CiAgICAgICAgICAgICAgICAgICAgICAgIH0KIAogICAgICAgICAgICAgICAgICAgICAgICB2MCA9IHYxOwogICAgICAgICAgICAgICAgICAgICAgICB2MSA9IG5leHRbdjBdOwogCiAgICAgICAgICAgICAgICAgICAgfSB3aGlsZSAodjAgIT0gMSk7CiAgICAgICAgICAgICAgICB9CiAKICAgICAgICAgICAgdXNlZFtiZXN0X3ZdID0gdHJ1ZTsKIAogICAgICAgICAgICBpbnQgdG1wID0gbmV4dFtiZXN0X3BsYWNlXTsKICAgICAgICAgICAgbmV4dFtiZXN0X3BsYWNlXSA9IGJlc3RfdjsKICAgICAgICAgICAgbmV4dFtiZXN0X3ZdID0gdG1wOwogCiAgICAgICAgICAgIG1heF9wYXRoX2xlbmd0aCArPSBiZXN0X2luY3JlYXNlOwogICAgICAgIH0KIAogICAgICAgIGNvdXQgPDwgIkNhc2UgIyIgPDwgdGVzdF9jYXNlIDw8ICI6ICIgPDwgbWF4X3BhdGhfbGVuZ3RoOwogICAgICAgIGlmICh0ZXN0X2Nhc2UgPCBUKQogICAgICAgICAgICBjb3V0IDw8ICdcbic7CiAgICB9Cn0=