#include <bits/stdc++.h>
using namespace std;
struct mulS
{
map<int, int> m;
int dif=0;
mulS(){};
mulS(int d)
{
m[0]=d;
}
};
struct nodS
{
int d;
mulS *mul;
vector<pair<int, int>> v;
};
int n,k,ans;
nodS nod[200005];
int getVal(mulS *a, int val)
{
val -= a->dif;
if(a->m.find(val) == a->m.end())
return -1;
return a->m[val];
}
void mergeMul(int d, mulS *&a, mulS *& b)
{
if(a->m.size() < b->m.size())
swap(a, b);
for(auto it : b->m)
{
int trVal = it.first + b->dif;
int oD = getVal(a, k - trVal);
if(oD != -1)
ans = min(ans, it.second + oD - 2*d);
}
for(auto it : b->m)
{
int nVal = it.first + b->dif - a->dif;
if(a->m.find(nVal) == a->m.end() || a->m[nVal] > it.second)
a->m[nVal] = it.second;
}
}
void dfs(int p, int par)
{
nod[p].d = nod[par].d+1;
nod[p].mul = new mulS(nod[p].d);
for(auto it : nod[p].v)
{
if(it.first == par)
continue;
dfs(it.first, p);
nod[it.first].mul->dif += it.second;
mergeMul(nod[p].d, nod[p].mul, nod[it.first].mul);
}
/*
if(p >= 9)
{
cout<<p<<":\n";
for(auto it : nod[p].mul->m)
cout<<it.first + nod[p].mul->dif<<' '<<it.second<<'\n';
cout<<'\n';
}
*/
}
int best_path(int N, int K, int h[][2], int l[])
{
n=N;
k=K;
for(int i=0;i<n-1;i++)
{
int x = h[i][0] + 1;
int y = h[i][1] + 1;
nod[x].v.push_back({y, l[i]});
nod[y].v.push_back({x, l[i]});
}
ans=1e9;
dfs(1, 0);
if(ans == 1e9)
return -1;
return ans;
}
