#include <bits/stdc++.h>
using namespace std;
#include "race.h"
//#define int long long
const int oo = 1e9;
#define quickly ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define print(a,l,r) for(int OK(l); OK <= r ; ++OK){ if(a[OK] < oo){cout << a[OK] <<' ';} else{cout << "- ";}} cout << '\n';
#define prints(a) for(auto i : a){ cout << i <<' ';} cout << '\n';
#define printz(a,l,r) for(int OK(1) ; OK <= l ; ++OK){for(int KO(1) ; KO <= r ; ++KO){if(a[OK][KO] < oo){cout << a[OK][KO] <<' ';}else{cout << "- ";}}cout << '\n';} cout << '\n';
#define fs first
#define sd second
#define ii pair<int, int>
#define iii pair<int, ii>
#define all(a) a.begin(), a.end()
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int MAX_HIGH = 1e6 + 5;
int n, k;
vector<ii> a[N];
int in = 0, minx = oo;
int high[N], best[MAX_HIGH], th[MAX_HIGH];
struct Centroid_decomposition{
int cen[N], sz[N];
int len[N];
void DFS_SZ(int u, int par){
sz[u] = 1;
for(ii e : a[u]){
int v = e.fs, w = e.sd;
if(v == par || cen[v]){
continue;
}
DFS_SZ(v, u);
sz[u] += sz[v];
}
}
void DFS_ANS(int u, int par, bool ok){
if(high[u] > k){
return;
}
if(!ok){
if(th[high[u]] != in){
th[high[u]] = in;
best[high[u]] = len[u];
}
else{
best[high[u]] = min(best[high[u]], len[u]);
}
}
else{
if(th[k - high[u]] == in){
minx = min(minx, best[k - high[u]] + len[u]);
}
}
for(ii e : a[u]){
int v = e.fs, c = e.sd;
if(v == par || cen[v]){
continue;
}
high[v] = high[u] + c;
len[v] = len[u] + 1;
DFS_ANS(v, u, ok);
}
}
int find_centroid(int u, int par, int mx){
for(ii e : a[u]){
int v = e.fs;
if(v == par || cen[v]){
continue;
}
if(sz[v] > mx / 2){
return find_centroid(v, u, mx);
}
}
return u;
}
void tree(int u){
DFS_SZ(u, 0);
int centroid = find_centroid(u, 0, sz[u]);
cen[centroid] = true;
++in;
len[centroid] = best[0] = high[centroid] = 0;
th[0] = in;
for(ii e : a[centroid]){
int v = e.fs, w = e.sd;
if(cen[v]){
continue;
}
high[v] = w;
len[v] = 1;
DFS_ANS(v, centroid, 1);
DFS_ANS(v, centroid, 0);
}
for(ii e : a[centroid]){
int v = e.fs;
if(!cen[v]){
tree(v);
}
}
}
};
Centroid_decomposition cen;
int best_path(int _n, int _k, int _h[][2], int _l[]){
n = _n;
k = _k;
for(int i(0) ; i < n - 1 ; ++i){
int u, v, w;
u = _h[i][0], v = _h[i][1], w = _l[i];
a[u + 1].push_back({v + 1, w});
a[v + 1].push_back({u + 1, w});
}
cen.tree(1);
if(minx == oo){
return -1;
}
return minx;
}
