#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]);
}
void print_best_path(int next[1000])
{
int v0 = 1;
int v1 = next[v0];
do
{
cout << v0 << " -> ";
v0 = v1;
v1 = next[v0];
} while (v0 != 1);
cout << "1\n";
}
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];
cout << "max_v=" << max_v << endl;
cout << "max_path_length=" << max_path_length << endl;
print_best_path(next);
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 << "best_v=" << best_v << " best_increase=" << best_increase <<
" max_path_length=" << max_path_length << endl;
print_best_path(next);
}
cout << "Case #" << test_case << ": " << max_path_length;
if (test_case < T)
cout << '\n';
}
}