#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int sz = 1e3 + 5;
int t;
int dp[15][sz], in[sz], out[sz], d[sz], e[sz];
vector<array<int, 2>> g[sz];
void dfs(int v, int p)
{
dp[0][v] = p;
in[v] = ++t;
for(auto i : g[v])
{
if(i[0] == p)continue;
d[i[0]] = d[v] + i[1];
e[i[0]] = e[v] + 1;
dfs(i[0], v);
}
out[v] = ++t;
}
bool anc(int u, int v)
{
return in[u] <= in[v] && out[v] <= out[u];
}
int lca(int u, int v)
{
if(anc(u, v))return u;
if(anc(v, u))return v;
for(int i = 10; i >= 0; i--)
{
if(anc(dp[i][v], u))continue;
v = dp[i][v];
}
return dp[0][v];
}
int dist(int u, int v)
{
return d[u] + d[v] - d[lca(u, v)] * 2;
}
int len(int u, int v)
{
return e[u] + e[v] - e[lca(u, v)] * 2;
}
int best_path(int n, int k, int h[][2], int l[])
{
for(int i = 0; i < n; i++)
{
int u = ++h[i][0], v = ++h[i][1], w = l[i];
g[u].pb({v, w});
g[v].pb({u, w});
}
dfs(1, 0);
for(int i = 1; i <= 10; i++)
{
for(int j = 1; j <= n; j++)
{
dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
}
int mn = 1e9 + 10;
for(int i = 1; i <= n; i++)
{
for(int j = i + 1; j <= n; j++)
{
if(dist(i, j) != k)continue;
mn = min(mn, len(i, j));
}
}
if(mn == 1e9 + 10)mn = -1;
return mn;
}
