#include<bits/stdc++.h>
#include "race.h"
#include<ext/pb_ds/assoc_container.hpp>
/**zagaro & lauren <3**/
#define mod 1000000007 //1e9 + 7
#define pi acos(-1)
#define wl while
#define str string
#define ENDL "\n"
#define sal ' '
#define tp_set ll
#define prc(n) cout.precision(n);cout<<fixed;
#define ord_set tree<tp_set, null_type, less<tp_set>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef bool bl;
typedef char car;
using namespace std;
using namespace __gnu_pbds;
ll n, r=LONG_LONG_MAX, k;
vector<vector<pair<ll,ll> > > adj;
vector<ll> sub;
vector<bl> vis;
ll centroid(ll nod, ll par, ll tam){
for(int i=0;i<adj[nod].size();i++){
if(adj[nod][i].first != par && vis[adj[nod][i].first]){
if(sub[adj[nod][i].first]*2 > tam){
return centroid(adj[nod][i].first, nod, tam);
}
}
}
return nod;
}
ll calc(ll nod, ll par){
sub[nod] = 1;
for(int i=0;i<adj[nod].size();i++){
if(adj[nod][i].first != par && vis[adj[nod][i].first]){
sub[nod] += calc(adj[nod][i].first, nod);
}
}
return sub[nod];
}
void dfs(ll nod, ll par, ll m, ll cdist, map<ll,ll> &mp){
if(cdist > k)return ;
if(mp[cdist] == 0)mp[cdist] = m;
else mp[cdist] = min(mp[cdist], m);
for(int i=0;i<adj[nod].size();i++){
if(adj[nod][i].first != par && vis[adj[nod][i].first]){
dfs(adj[nod][i].first, nod, m+1, cdist+adj[nod][i].second, mp);
}
}
return ;
}
void build(ll nod){
ll x = centroid(nod, -1, calc(nod, -1));
vis[x]=false;
map<ll,pair<ll,ll> > tot;
vector<map<ll,ll> > mp(adj[x].size());
for(int i=0;i<adj[x].size();i++){
if(vis[adj[x][i].first]){
dfs(adj[x][i].first, x, 1, adj[x][i].second, mp[i]);
pair<ll,ll> p;
for(auto w: mp[i]){
p = tot[w.first];
if(p.first == 0)tot[w.first].first = w.second;
else if(p.second == 0)tot[w.first].second = w.second;
else if(w.second <= p.first){
tot[w.first].first = w.second;
tot[w.first].second = p.first;
}
else if(w.second < p.second)tot[w.first].second = w.second;
}
build(adj[x][i].first);
}
}
if(tot[k].first != 0)r = min(r, tot[k].first);
for(int i=0;i<adj[x].size();i++){
for(auto w: mp[i]){
if(tot[k-w.first].first == 0)continue;
if(tot[k-w.first].first == (*mp[i].find(k-w.first)).second){
if(tot[k-w.first].second != 0)r = min(r, tot[k-w.first].second + w.second);
}
else r = min(r, tot[k-w.first].first + w.second);
}
}
return ;
}
int best_path(int N, int K, int H[][2], int L[]){
ll a, b, v;
n = N;k = K;
adj.assign(n+1, vector<pair<ll,ll> > (0, {0, 0}));
sub.assign(n+1, 1);
vis.assign(n+1, true);
for(int i=0;i<n-1;i++){
a = H[i][0]+1;
b = H[i][1]+1;
v = L[i];
adj[a].push_back({b, v});
adj[b].push_back({a, v});
}
build(1);
if(r == LONG_LONG_MAX)return -1;
return r;
}
