#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define A first
#define B second
#define MP make_pair
#define ms(a, x) memset(a, x, sizeof(a))
#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("trapv")
#define boost() ios_base::sync_with_stdio(false); cin.tie(0)
typedef __int128_t vl;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<long double, long double> pld;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
const int mxN=2e5+5, LOG=21;
vector <vector<pii>> adj(mxN);
int sz[mxN], cnt[int(1e6)+5], ans=INF;
bool mark[mxN];
void dfs_sz(int u, int p){
sz[u]=1;
for(auto [v, x]:adj[u]){
if(v == p || mark[v]) continue;
dfs_sz(v, u);
sz[u] += sz[v];
}
return;
}
int dfs_cntrd(int u, int p, int subsz){
for(auto [v, x]:adj[u]){
if(v == p || mark[v]) continue;
if(sz[v] > subsz/2) return dfs_cntrd(v, u, subsz);
}
return u;
}
void dfs_cnt(int u, int x, int d, int p, int mode, int k){
if(x > k) return;
(mode ? (mode == 1 ? ans = min(ans, d+cnt[k-x]):cnt[x]=INF):cnt[x] = min(cnt[x], d));
for(auto [v, dist]:adj[u]){
if(mark[v] || v == p) continue;
dfs_cnt(v, dist+x, d+1, u, mode, k);
}
}
void decompose(int u, int subsz, int k){
dfs_sz(u, -1);
int cntrd = dfs_cntrd(u, -1, subsz);
mark[cntrd]=1;
for(auto [v, x]:adj[cntrd]){
if(mark[v]) continue;
dfs_cnt(v, x, 1, -1, 1, k);
dfs_cnt(v, x, 1, -1, 0, k);
}
ans = min(ans, cnt[k]);
for(auto [v, x]:adj[cntrd]){
if(mark[v]) continue;
dfs_cnt(v, x, 1, -1, 2, k);
}
for(auto [v, x]:adj[cntrd]){
if(mark[v]) continue;
decompose(v, sz[v], k);
}
return;
}
int best_path(int n, int k, int h[mxN][2], int l[mxN]){
ms(cnt, INF);
for(int i=0; i<n-1; i++){
adj[h[i][0]+1].push_back({h[i][1]+1, l[i]});
adj[h[i][1]+1].push_back({h[i][0]+1, l[i]});
}
decompose(1, n, k);
if(ans == INF) return -1;
else return ans;
}
