#include <bits/stdc++.h>
#define pii pair < int , int >
using namespace std;
const int N = 2e5 + 10;
set < pii > G[N];
int sz[N];
int a[N * 10];
int K;
void getsize(int node , int par)
{
sz[node] = 1;
for(auto to : G[node])
if(to.first != par)
{
getsize(to.first , node);
sz[node] += sz[to.first];
}
}
int find(int node , int par , int n)
{
for(auto to : G[node])
if(to.first != par)
{
if(sz[to.first] > n / 2)
return find(to.first , node , n);
}
return node;
}
int ans = INT_MAX;
void get(int node , int par , int len , int h)
{
if(len <= K && a[K - len])
ans = min(ans , a[K - len] + h - 1);
if(len == K)
ans = min(ans , h - 1);
for(auto to : G[node])
if(to.first != par)
get(to.first , node , len + to.second , h + 1);
}
void add(int node , int par , int len , int h)
{
if(len <= K)
{
if(a[len] == 0) a[len] = h - 1;
else a[len] = min(a[len] , h - 1);
}
for(auto to : G[node])
if(to.first != par)
add(to.first , node , len + to.second , h + 1);
}
void solve(int root)
{
for(int i = 0 ; i <= K ; i++)
a[i] = 0;
for(auto to : G[root])
{
get(to.first , root , to.second , 2);
add(to.first , root , to.second , 2);
}
}
void decomp(int root)
{
getsize(root , 0);
int c = find(root , 0 , sz[root]);
solve(c);
for(auto to : G[c])
{
G[to.first].erase({c , to.second});
decomp(to.first);
}
}
int best_path(int n , int k , int H[][2] , int L[])
{
K = k;
for(int i = 0 ; i < n - 1 ; i++)
{
int x = H[i][0];
int y = H[i][1];
G[x].insert({y , L[i]});
G[y].insert({x , L[i]});
}
decomp(0);
if(ans == INT_MAX) ans = -1;
return ans;
}
