#include "race.h"
//~ #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
typedef vector<int> vi;
typedef vector<double> vd;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<vi> vv;
const int inf = 1e9, mxN = 2e5+2;
vii g[mxN];
int us[mxN];
int m, ctr, ans = inf;
int n, k, k2;
int dfs_sz(int v, int pr){
if(us[v])return 0;
int s = 1;
for(auto [to, cst]:g[v]){
if(to == pr)continue;
s += dfs_sz(to, v);
}
return s;
}
int dfs_ctr(int v, int pr){
if(us[v])return 0;
int s = 1;
bool ok = 1;
for(auto [to, cst]:g[v]){
if(to == pr)continue;
int sto = dfs_ctr(to, v);
if(sto > m/2)ok = 0;
s += sto;
}
if(s < m/2)ok = 0;
if(ok)ctr = v;
return s;
}
void dfs(int v, int pr, int dep, int sum, vector<pair<int,int>> &ds){
if(us[v] || sum > k)return;
ds.pb({sum, dep});
for(auto [to, cst]:g[v]){
if(to == pr)continue;
dfs(to, v, dep+1, sum + cst, ds);
}
}
void calc(int &v){
unordered_map<int,int> mp;
for(auto [to, cst]:g[v]){
if(us[to])continue;
vector<pair<int,int> > ds;
dfs(to, v, 1, 0, ds);
for(auto j:ds)ans = min(ans, (mp[k-j.ff] == 0 ? inf : mp[k-j.ff]) + j.ss);
for(auto j:ds){
if(mp[j.ff] == 0)mp[j.ff] = j.ss;
else mp[j.ff] = min(mp[j.ff], j.ss);
}
}
}
void fun(int v){
m = dfs_sz(v, -1);
m = dfs_ctr(v, -1);
us[ctr] = 1;
calc(ctr);
for(auto [to, cst]:g[ctr]){
if(!us[to])fun(to);
}
}
int best_path(int n, int k, int h[][2], int l[])
{
for(int i = 0; i < n-1; i++){
g[h[i][0]].pb({h[i][1], l[i]});
g[h[i][1]].pb({h[i][0], l[i]});
}
fun(0);
return ans;
}
