#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int n, nn, k;
bitset<200010> al;
vector<pair<int, int> > adj[200010];
vector<int> ch[200010];
int p[200010], sz[200010], d[200010];
long long cost[200010];
set<pair<int, int> > s[200010];
const int lgmx = 18;
int sp[18][200010];
const int INF = 1e9;
int ans = INF;
void dfs(int u, int pp = -1){
sp[0][u] = pp;
for(int i = 1; i < lgmx; i++)
if(sp[i - 1][u] != -1) sp[i][u] = sp[i - 1][sp[i - 1][u]];
for(auto k : adj[u]){
int v, w; tie(v, w) = k;
if(v == pp) continue;
d[v] = d[u] + 1;
cost[v] = cost[u] + w;
dfs(v, u);
}
}
int lca(int u, int v){
if(d[u] < d[v]) swap(u, v);
bitset<lgmx> diff = d[u] - d[v];
for(int i = lgmx - 1; i >= 0; i--)
if(diff[i]) u = sp[i][u];
if(u == v) return v;
for(int i = lgmx - 1; i >= 0; i--){
if(sp[i][u] != sp[i][v]){
u = sp[i][u], v = sp[i][v];
}
}
return sp[0][v];
}
pair<long long, int> getDist(int u, int v){
int a = lca(u, v);
return {cost[u] + cost[v] - (cost[a] << 1), d[u] + d[v] - (d[a] << 1)};
}
void findSz(int u, int pp = -1){
sz[u] = 1;
nn++;
for(auto k : adj[u]){
int v = k.first;
if(al[v] || v == pp) continue;
findSz(v, u);
sz[u] += sz[v];
}
}
int findCentroid(int u, int pp = -1){
for(auto k : adj[u]){
int v = k.first;
if(al[v] || v == pp || sz[v] <= nn) continue;
return findCentroid(v, u);
}
return u;
}
void decompose(int u, int pp = -1){
nn = 0;
findSz(u);
nn >>= 1;
int x = findCentroid(u);
p[x] = pp;
al[x] = 1;
for(auto k : adj[x]){
int v = k.first;
if(!al[v]) decompose(v, x);
}
}
void update(int u){
int x = u;
while(p[x] != -1){
long long tp; int len;
tie(tp, len) = getDist(u, p[x]);
// cerr << u << " " << x << " " << p[x] << " " << tp << " " << len << endl;
s[x].insert({tp, len});
x = p[x];
}
}
void query(int u){
int x = u;
for(auto v : ch[u]){
auto it = s[v].lower_bound({k, -1});
if(it -> first == k) ans = min(ans, it -> second);
}
while(p[x] != -1){
long long tp; int len;
tie(tp, len) = getDist(u, p[x]);
// cerr << "Q: " << u << " " << x << " " << p[x] << " " << tp << " " << len << endl;
if(tp > k) return;
for(auto v : ch[p[x]]){
if(v == x) continue;
auto it = s[v].lower_bound({k - tp, -1});
// cerr << v << " " << (it -> first) << " " << (it -> second) << endl;
if(it -> first == k - tp) ans = min(ans, len + it -> second);
}
x = p[x];
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N, k = K;
for(int i = 0; i < n - 1; i++){
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
memset(sp, -1, sizeof(sp));
dfs(0);
decompose(0);
for(int i = 0; i < n; i++){
if(p[i] != -1) ch[p[i]].emplace_back(i);
//cerr << i << " <- " << p[i] << endl;
}
for(int i = 0; i < n; i++) update(i);
for(int i = 0; i < n; i++) query(i);
if(ans == INF) ans = -1;
return ans;
}
