#include "race.h"
//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define spc " "
#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#else
#define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#endif
const double PI = acos(-1);
const int MOD = 1000000007;
const int inf = (2147483647);
int ans = inf;
class centroid_decomposition{
private:
vi dead, sub;
vector<vector<pii>> adj;
unordered_map<int, int> mp, add;
int K;
public:
centroid_decomposition(int n, vector<vector<pii>> &_adj, int _K){
adj = _adj;
K = _K;
dead.resize(n+1, 0);
sub.resize(n+1);
build(0);
}
void build(int u){
int n = child(u);
int cent = centroid(n, u);
mp.clear();
mp[0] = 0;
dead[cent] = 1;
for(auto v: adj[cent]){
if(dead[v.ff]) continue;
checkAns(v.ff, cent, v.ss, 1);
for(auto x: add) mp[x.ff] = min(mp.find(x.ff)!=mp.end() ? mp[x.ff] : inf, x.ss);
add.clear();
// AddAns(v.ff, cent, v.ss, 1);
}
for(auto v: adj[cent]){
if(!dead[v.ff]) build(v.ff);
}
return;
}
void checkAns(int u, int p, int gone, int cnt){
if(gone > K) return;
int need = K-gone;
if(mp.find(need)!=mp.end()) ans = min(cnt+mp[need], ans);
if(add.find(gone)!=add.end()) add[gone] = min(add[gone], cnt);
else add[gone] = cnt;
for(auto x: adj[u])
if(!dead[x.ff] && x.ff!=p) checkAns(x.ff, u, gone+x.ss, cnt+1);
return;
}
void AddAns(int u, int p, int gone, int cnt){\
if(gone > K) return;
for(auto x: adj[u])
if(!dead[x.ff] && x.ff!=p) AddAns(x.ff, u, gone+x.ss, cnt+1);
return;
}
int child(int u, int p = -1){
sub[u] = 1;
for(auto v: adj[u])
if(!dead[v.ff] && v.ff!=p) sub[u] += child(v.ff, u);
return sub[u];
}
int centroid(int n, int u, int p = -1){
for(auto v: adj[u])
if(!dead[v.ff] && v.ff!=p && sub[v.ff]>n/2) return centroid(n, v.ff, u);
return u;
}
};
int best_path(int N, int K, int H[][2], int L[])
{
ans = inf;
vector<vector<pii>> adj(N+1);
for(int i = 0; i < N-1; i++){
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
centroid_decomposition cd(N, adj, K);
if(ans==inf) return -1;
return ans;
}
