#include "race.h"
#include <bits/stdc++.h>
#define N 200000
#define MAX 1000000000
#define E 0.00000001
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFll 0x3f3f3f3f3f3f3f3fll
#define LEFT(x) (2 * x)
#define RIGHT(x) (2 * x + 1)
#define se second
#define fi first
using namespace std;
typedef long long ll;
vector<int> g[N+1];
map<pair<int,int>, ll> e;
map<ll,int, greater<ll>> d[N+1];
ll dist[N+1];
int sz[N+1];
int ans = -1;
void prec(ll u, ll p){
if(u != 1) dist[u] = dist[p] + e[{u,p}];
for(ll v : g[u]){
if(v == p) continue;
prec(v, u);
}
}
void solve(int u, int p, int depth, ll k){
int big = -1;
sz[u] = 1;
for(int v : g[u]){
if(v == p) continue;
solve(v, u, depth+1, k);
sz[u] += sz[v];
if(big == -1 or sz[v] > sz[big]) big = v;
}
if(big == -1){
d[u][dist[u]] = depth;
return;
}
swap(d[u], d[big]);
d[u][dist[u]] = depth;
for(int v : g[u]){
if(v == p or v == big) continue;
for(auto i : d[v]){
ll want = k + 2 * dist[u] - i.fi;
if(d[u].count(want)){
if(ans == -1) ans = (i.se - depth) + (d[u][want] - depth);
else ans = min(ans, (i.se - depth) + (d[u][want] - depth));
}
}
for(auto i : d[v]){
if(d[u].count(i.fi)){
d[u][i.fi] = min(d[u][i.fi], i.se);
}
else{
d[u][i.fi] = i.se;
}
}
}
if(d[u].count(k + dist[u])){
if(ans == -1) ans = d[u][k + dist[u]] - depth;
else ans = min(ans, d[u][k + dist[u]] - depth);
}
}
int best_path(int n, int k, int (*h)[2], int* l){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
for(ll i = 0; i <= n; i++){
g[i].clear();
dist[i] = 0;
sz[i] = 0;
d[i].clear();
}
ans = -1;
e.clear();
for(ll i = 0; i < n-1; i++){
ll u, v, w;
u = h[i][0];
v = h[i][1];
w = l[i];
u++;
v++;
g[u].push_back(v);
g[v].push_back(u);
e[{u,v}] = w;
e[{v,u}] = w;
}
prec(1,0);
solve(1, 0, 0, k);
return ans;
}
