#include <bits/stdc++.h>
#define pb push_back
#define spc << " " <<
#define endl "\n"
#define all(x) x.begin(), x.end()
#define ll long long
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define mid (l+r)/2
#define inf 1e9
#define MOD 998244353
#define MX 500005
using namespace std;
vii edges[MX];
int tin[MX], tout[MX], dep[MX], depfr[MX], par[MX][20], mark[MX], sub[MX];
vi chil[MX];
int tim=0, og=-1;
int k;
void upd(int node, int pa){
sub[node]=1;
for(auto p:edges[node]){
if(p.st==pa || mark[p.st]) continue;
upd(p.st, node);
sub[node]+=sub[p.st];
}
}
int cent(int node){
upd(node, node);
int cur=node, las=node;
int flag;
while(true){
flag=1;
for(auto i:edges[cur]){
if(mark[i.st] || i.st==las) continue;
if(sub[i.st]>sub[node]/2){
las = cur;
cur = i.st;
flag=0;
break;
}
}
if(flag) break;
}
mark[cur]=1;
if(og==-1) og=cur;
for(auto p:edges[cur]){
if(mark[p.st]) continue;
chil[cur].pb(cent(p.st));
}
return cur;
}
void dfs(int node, int pa){
tin[node] = ++tim;
par[node][0]=pa;
for(int i=1; i<20; i++) par[node][i] = par[par[node][i-1]][i-1];
for(auto p:edges[node]){
if(p.st==pa) continue;
dep[p.st] = dep[node] + p.nd;
depfr[p.st] = depfr[node] + 1;
dfs(p.st, node);
}
tout[node] = tim;
}
bool anc(int u, int v){
return tin[u]<=tin[v] && tout[u]>=tout[v];
}
int lca(int u, int v){
if(u==v) return u;
if(dep[v]>dep[u]) swap(u,v);
for(int i=19; i>=0; i--) if(!anc(par[u][i], v)) u = par[u][i];
return par[u][0];
}
ii dis(int u, int v){
int tem = lca(u,v);
return {dep[u]+dep[v]-2*dep[tem], depfr[u]+depfr[v]-2*depfr[tem]};
}
vi wow[MX];
int dfs2(int node){
wow[node].pb(node);
if(!chil[node].size()) return inf;
int ind=0, maxi=0, res=inf;
for(auto i:chil[node]){
res = min(res, dfs2(i));
if(wow[i].size()>maxi) ind=i;
}
wow[node].swap(wow[ind]);
for(auto i:chil[node]){
if(i==ind) continue;
for(auto j:wow[i]) wow[node].pb(j);
}
map<int, int> heh;
for(auto i:wow[node]){
ii d=dis(node, i);
if(heh[k-d.st]!=0){
res = min(res, heh[k-d.st]+d.nd);
}
if(heh[d.st]==0 || d.nd<heh[d.st]) heh[d.st]=d.nd;
}
wow[node].pb(node);
return res;
}
int best_path(int N, int K, int H[][2], int L[]){
k=K;
for(int i=0; i<N-1; i++){
edges[H[i][1]].pb({H[i][0],L[i]});
edges[H[i][0]].pb({H[i][1],L[i]});
}
memset(mark, 0, sizeof(mark));
dep[0]=depfr[0]=0;
dfs(0,0);
cent(0);
int lol = dfs2(og);
if(lol==inf) return -1;
return lol;
}
