#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define task "sus"
#define pii pair<int,int>
const int MN = 2e5+5,inf = 1e9,MX = 1e6+5;
vector<pii> adj[MN];
int cnt_child[MN],res = inf,k;
bool del[MN];
void find_cnt_child(int u,int p)
{
cnt_child[u] = 1;
for(auto e:adj[u]){
int v = e.first;
if(v!=p and !del[v]){
find_cnt_child(v,u);
cnt_child[u] += cnt_child[v];
}
}
}
int find_centroid(int u,int p,int n)
{
for(auto e:adj[u]){
int v = e.first;
if(v!=p and !del[v] and cnt_child[v]>n/2)
return find_centroid(v,u,n);
}
return u;
}
int dist[MN],best_dist[MX],h[MN];
void dfs1(int u,int p,bool sta)
{
if(sta){
if(dist[u]==k) res = min(res,h[u]);
if(dist[u]<k and best_dist[k-dist[u]])
res = min(res,best_dist[k-dist[u]]+h[u]);
}
else{
if(dist[u]<=k) {
if(best_dist[dist[u]]==0) best_dist[dist[u]] = h[u];
else best_dist[dist[u]] = min(best_dist[dist[u]],h[u]);
}
}
for(auto e:adj[u]){
int v = e.first;
int w = e.second;
if(del[v] or v==p) continue;
h[v] = h[u]+1;
dist[v] = dist[u] + w;
dfs1(v,u,sta);
}
}
void dfs2(int u,int p)
{
if(dist[u]<=k) {
best_dist[dist[u]] = 0;
dist[u] = 0;
}
for(auto e:adj[u]) if(!del[e.first] and e.first!=p) dfs2(e.first,u);
}
void upd_ans(int u)
{
dist[u] = 0;
for(auto e:adj[u]){
int v = e.first;
int w = e.second;
if(del[v]) continue;
h[v] = 1;
dist[v] = w;
dfs1(v,u,1);
dfs1(v,u,0);
}
dfs2(u,0);
}
void sol(int u)
{
find_cnt_child(u,0);
int n = cnt_child[u];
int root = find_centroid(u,0,n);
//cerr << "SOLVING: " << u << ' ' << root << ' ' << n << endl;
del[root] = 1;
upd_ans(root);
//cerr << "ANS: " << res << endl;
for(auto e:adj[root]) if(!del[e.first]) sol(e.first);
}
int best_path(int n,int K,int h[][2],int l[])
{
k = K;
for(int i=0; i<n-1; i++){
int u,v;
u = h[i][0]; v = h[i][1];
adj[u].push_back({v,l[i]});
adj[v].push_back({u,l[i]});
}
sol(0);
if(res!=inf) return res;
return -1;
}
//
//signed main()
//{
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// if(fopen(task".inp","r")){
// freopen(task".inp","r",stdin);
// freopen(task".out","w",stdout);
// }
// int n,k,h[MN][2],l[MN];
// cin >> n >> k;
// for(int i=0; i<n-1; i++) cin >> h[i][0] >> h[i][1];
// for(int i=0; i<n-1; i++) cin >> l[i];
// cout << best_path(n,k,h,l);
// cerr << "\nTIME: " << clock() << '\n';
//}
