#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define eb emplace_back
#define pb pop_back
#define em emplace
#define sz(x) ((ll)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define upmin(x,y) x=min(x,y)
#define upmax(x,y) x=max(x,y)
typedef long long ll;
typedef pair <int,int> pii;
int inf = INT_MAX;
ll llinf = LLONG_MAX;
int N,K,L[200003];
int par[200003],sz[200003];
vector <pii> adj[200003];
int check[1000003];
bool del[200003];
int ans = 1987654321;
vector <pii> lazy;
vector <int> usecheck;
int dfs1(int now,int prev)
{
sz[now] =0;
for(auto it : adj[now])
{
int next = it.first;
if(next == prev) continue;
if(del[next]) continue;
sz[now] += dfs1(next,now);
}
return ++sz[now];
}
int find_cen(int now,int prev,int root)
{
for(auto it : adj[now])
{
int next = it.fi;
if(next == prev) continue;
if(del[next]) continue;
if(sz[next]*2>sz[root]) return find_cen(next,now,root);
}
return now;
}
int dfs2(int now,int prev,int sum,int depth,int maxans=1987654321)
{
if(depth>=maxans) return 1987654321;
int ret = 1987654321;
if(sum>K) return 1987654321;
if(check[K-sum]!=1987654321) upmin(ret,depth + check[K-sum]);
lazy.eb(sum,depth);
for(auto it : adj[now])
{
int next = it.fi;
int cost = it.se;
if(next == prev) continue;
if(del[next]) continue;
upmin(ret,dfs2(next,now,sum+cost,depth+1,ret));
if(sum==0)
{
for(pii it:lazy) upmin(check[it.first],it.second),usecheck.eb(it.first);
lazy.clear();
}
}
return ret;
}
void g(int now,int prev)
{
dfs1(now,-1);
int cen = find_cen(now,-1,now);
for(int it:usecheck) check[it] = 1987654321;
usecheck.clear();
check[0] = 0;
upmin(ans,dfs2(cen,-1,0,0));
del[cen] = true;
for(auto it : adj[cen])
{
if(del[it.fi]) continue;
g(it.fi,now);
}
}
int best_path(int n, int k, int h[][2], int l[])
{
fill(check,check+1000003,1987654321);
N= n ; K = k;
for(int i=0;i<n-1;i++)
{
adj[h[i][0]].eb(pii(h[i][1],l[i]));
adj[h[i][1]].eb(pii(h[i][0],l[i]));
}
g(1,-1);
return (ans>=1987654300)?-1:ans;
}
