#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll long long
#define f first
#define s second
//https://ioi.contest.codeforces.com/group/32KGsXgiKA/contest/103758/problem/B
void setIO(string name="") {
cin.tie(0)->sync_with_stdio(0);
if (!name.empty()) {
freopen((name+".in").c_str(), "r", stdin);
freopen((name+".out").c_str(), "w", stdout);
}
}
vector<vector<pair<int,int>>> sus; //vertex, dist
vector<int> mam,subtr;
int SUBTR_SZ;
int K;
int dfs(int cur,int par = -1){
subtr[cur] = 1;
for(auto i : sus[cur])if(i.f != par && !mam[i.f]){
subtr[cur] += dfs(i.f,cur);
}
return subtr[cur];
}
int find_centroid(int cur,int par = -1){
for(auto i : sus[cur])if(i.f != par && !mam[i.f]){
if(subtr[i.f]*2 > SUBTR_SZ) return find_centroid(i.f,cur);
}
return cur;
}
void calculate_d(int cur,map<int,int> &dists,int par = -1,int d = 0,int k = 0){
if(d > K) return;
if(dists.find(d) == dists.end()) dists[d] = k;
else dists[d] = min(dists[d],k);
for(auto i : sus[cur])if(i.f != par && !mam[i.f]){
calculate_d(i.f,dists,cur,d + i.s,k+1);
}
}
int solve(int cur){
//cerr<<cur<<endl;
int ans = 1<<30;
SUBTR_SZ = dfs(cur);
if(SUBTR_SZ == 1) return 1<<30;
int centroid = find_centroid(cur);
//cerr<<"centroid "<<centroid<<endl;
vector<int> moje_d(K+1,1<<30);
moje_d[0] = 0;
mam[centroid] = 1;
for(auto i : sus[centroid])if(!mam[i.f]){
map<int,int> tmp_d;
calculate_d(i.f,tmp_d,centroid,i.s,1);
//cerr<<"cur d: "<<i.f<<" ";
//for(auto i : tmp_d)cerr<<i.f<<";"<<i.s<<" ";cerr<<endl;
for(auto i : tmp_d)if(K - i.f >= 0 && moje_d[K - i.f] != 1<<30){
ans = min(ans,moje_d[K - i.f] + i.s);
}
for(auto i : tmp_d){
moje_d[i.f] = min(moje_d[i.f],i.s);
}
}
for(auto i : sus[centroid])if(!mam[i.f]){
ans = min(ans,solve(i.f));
}
return ans;
}
int best_path(int n,int k,int edges[][2],int weights[]){
sus.resize(n);
mam.resize(n,0);
subtr.resize(n);
K = k;
for(int i = 0;i<n-1;i++){
sus[edges[i][0]].push_back({edges[i][1],weights[i]});
sus[edges[i][1]].push_back({edges[i][0],weights[i]});
}
int ans = solve(0);
return ans == 1<<30 ? -1 : ans;
}
