#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,MOD=1e9+7;
#define ll long long
#define yes {cout<<"YES";return;}
#define no {cout<<"NO";return;}
#define srt(a,n) sort(a+1,a+n+1);
#define srt2(a,n,comp) sort(a+1,a+n+1,comp);
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define MAXN 1000005
int n,k;
vector <pair <int,int>> s[N];
int sz[N],high[N],dist[N],par[N];
bool visited[N];
int exist[MAXN];
int Save[MAXN];
int thutu = 0;
vector <pair <int,int>> tmp;
int res = 1e9;
int dfs(int i, int pre){
sz[i] = 1;
for (auto x: s[i]){
if (x.fi == pre || visited[x.fi])
continue;
dist[x.fi] = dist[i] + x.se;
sz[i] += dfs(x.fi,i);
}
return sz[i];
}
int Find_Centroid(int i, int pre, int Size){
for (auto x: s[i]){
if (x.fi == pre || visited[x.fi])
continue;
if (sz[x.fi] > Size/2)
return Find_Centroid(x.fi,i,Size);
}
return i;
}
int dfs2(int i, int pre, int cnt, int d, int l){
int ans = 1e9;
if (d <= k && exist[k - d] == cnt){
ans = min(ans, l + Save[k-d]);
}
if (d <= k){
tmp.pb({d,l});
for (auto x: s[i]){
if (visited[x.fi] || x.fi == pre)
continue;
ans = min(ans, dfs2(x.fi,i,cnt,d + x.se,l + 1));
}
}
return ans;
}
void Build_Centroid(int u,int p){
int cnt = ++thutu;
int Size = dfs(u,u);
int centroid = Find_Centroid(u,u,Size);
visited[centroid] = true;
exist[0] = cnt;
Save[0] = 0;
for (auto x: s[centroid]){
if (visited[x.fi])
continue;
tmp.clear();
res = min(res, dfs2(x.fi,centroid,cnt,x.se,1));
for (auto v: tmp){
int i = v.fi;
int j = v.se;
if (exist[i] < cnt){
exist[i] = cnt;
Save[i] = j;
}
if (Save[i] > j)
Save[i] = j;
}
}
visited[centroid] = true;
for (auto x: s[centroid]){
if (visited[x.fi])
continue;
Build_Centroid(x.fi,u);
}
}
int best_path(int _n, int _k, int h[][2], int L[])
{
n = _n; k = _k;
for (int i = 1;i < n;i++){
int u,v,l;
u = h[i - 1][0];
v = h[i - 1][1];
l = L[i - 1];
s[u].pb({v,l});
s[v].pb({u,l});
}
Build_Centroid(1,0);
if (res == 1e9)
return -1;
else return res;
}
