#include <bits/stdc++.h>
using namespace std;
// types - only for stuff used a lot
using ll = long long;
#define vv vector
#define Pp pair
// IO
#define get(x) scanf("%d",&x)
#define getl(x) scanf("%lld",&x);
// Operations
#define pb push_back
#define pob pop_back
#define sz(a) int(a.size())
#define re(a,b) a=max(a,b) // relax
#define ri(a,b) a=min(a,b) // relaxi
// Debugging
#ifndef LOCAL
#define cerr if (0) cerr
#else
#define cerr cout
#endif
#define print(arr,n) {for (int _ = 0; _ < n; _++) cerr<<arr[_]<<" "; cerr << endl; }
#define printv(vec) {for (int _ : vec) cerr<<_<<" "; cerr<<endl;}
const int mod = 1e9+7, oo = 1e9;
const ll loo = 1e18;
// Functions
ll modpow(ll a, ll b) {
ll ans = 1; // faster modpow than recursive
for (; b; b/=2,a=a*a%mod)
if (b&1) ans = (ans*a)%mod;
return ans;
}
ll gcd(ll a, ll b) {
while (a) b%=a,swap(a,b);
return b;
}
#define bitcount __builtin_popcountll
#define f(i,a,b) for (int i = a; i < b; i++)
#define fr(i,a,b) for (int i = b-1; i >= a; i--)
/*
ALRIGHT HACKERS, THIS IS WHERE THE ACTUAL CODE BEGINS
*/
const bool DEBUG = 1;
using vi = vector<int>;
const int N = 200000;
map<int,int> freq;
int K;
int ans = oo;
vi adj[N];
int a[N],b[N],c[N];
int sz[N];
int dfs_subsz(int v, int p) {
sz[v] = 1;
for (int e : adj[v]) {
int w = a[e]^b[e]^v;
if (w != p)
sz[v] += dfs_subsz(w,v);
}
return sz[v];
}
void explore(int v, int p, int d, int dd) {
if (freq.count(K-d))
ri(ans,dd+freq[K-d]);
for (int e : adj[v]) {
int w = a[e]^b[e]^v;
if (w != p) explore(w,v,d+c[e],dd+1);
}
}
void add(int v, int p, int d, int dd) {
if (!freq.count(d))
freq[d] = oo;
ri(freq[d],dd);
if (freq.count(K-d))
ri(ans,dd + freq[K-d]);
for (int e : adj[v]) {
int w = a[e]^b[e]^v;
if (w != p) add(w,v,d+c[e],dd+1);
}
}
void dfs_solve(int v, int p, bool keep) {
int bigChild = -1, bigSz = -1;
for (int e : adj[v]) {
int w = a[e]^b[e]^v;
if (w != p && sz[w] > bigSz)
bigSz = sz[w], bigChild = w;
}
for (int e : adj[v]) {
int w = a[e]^b[e]^v;
if (w != p && w != bigChild)
dfs_solve(w,v,0);
}
if (bigChild != -1) dfs_solve(bigChild,v,1);
if (freq.count(K)) ri(ans,freq[K]);
freq[0] = 0;
for (int e : adj[v]) {
int w = a[e]^b[e]^v;
if (w != p && w != bigChild) {
explore(w,v,c[e],1);
add(w,v,c[e],1);
}
}
if (!keep)
freq = map<int,int>();
}
int best_path(int n, int k, int h[][2], int l[]) {
f(i,0,n-1) {
a[i] = h[i][0], b[i] = h[i][1], c[i] = l[i];
adj[a[i]].pb(i); adj[b[i]].pb(i);
}
dfs_subsz(0,-1);
dfs_solve(0,-1,0);
return ans==oo?-1:ans;
}
