#include "race.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define meta int tm = (tl + tr) / 2, x = i * 2 + 1, y = x + 1
const int N = 2e5 + 7;
const int TN = 4 * N;
const int oo = 1e9;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
int n, k, p[30][N], d[30][N], lvl[N], mn = oo, pw[30];
vii v[N];
void dfs (int o, int par) {
for (auto c : v[o]) {
if (c.ff == par) continue;
lvl[c.ff] = lvl[o] + 1;
p[0][c.ff] = o;
d[0][c.ff] = c.ss;
dfs(c.ff, o);
}
}
pii distance (int x, int y) {
if (lvl[x] > lvl[y])
swap(x, y);
int d1 = 0, d2 = 0;
for (int i = 20; i >= 0; i--) {
if (lvl[y] - lvl[x] >= pw[i]) {
d1 += d[i][y];
d2 += pw[i];
y = p[i][y];
}
}
for (int i = 20; i >= 0; i--) {
if (p[i][x] != p[i][y]) {
d1 += d[i][x] + d[i][y];
d2 += pw[i] + pw[i];
x = p[i][x];
y = p[i][y];
}
}
if (x != y) {
d1 += d[0][x] + d[0][y];
d2 += 2;
}
return {d1, d2};
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for (int i = 0; i < n; i++) {
v[H[i][0]].pb({H[i][1], L[i]});
v[H[i][1]].pb({H[i][0], L[i]});
}
pw[0] = 1;
for (int i = 1; i <= 20; i++)
pw[i] = pw[i - 1] * 2;
dfs(0, 0);
for (int i = 1; i <= 20; i++) {
for (int j = 0; j < n; j++) {
p[i][j] = p[i - 1][p[i - 1][j]];
d[i][j] = d[i - 1][j] + d[i - 1][p[i - 1][j]];
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
pii pr = distance(i, j);
if (pr.ff == k) {
if (pr.ss < mn) mn = pr.ss;
}
}
}
if (mn == oo) return -1;
return mn;
}
