///~~~LOTA~~~///
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define MAXN 200000
int o,D;
int pwr[18];
int siz[MAXN];
int dpt[MAXN];
int mark[MAXN];
int dept[MAXN];
map<int,int> z;
int par[MAXN][18];
vector<pii> a[MAXN];
pii get_dist(int v,int u){
int x,y,p,q;
x=v;
y=u;
if(dpt[v]>dpt[u]) swap(v,u);
for(int i=17;i>=0;i--){
if(par[v][i]>=0){
if(dpt[par[v][i]]>=dpt[u])
v=par[v][i];
}
}
for(int i=17;i>=0;i--){
if(par[v][i]!=par[u][i]){
v=par[v][i];
u=par[v][i];
}
}
if(v!=u){
v=par[v][0];
u=par[u][0];
}
p=dept[x]+dept[y]-2*dept[v];
q=dpt[x]+dpt[y]-2*dpt[v];
return {p,q};
}
void dfs2(int v,int u,int d){
siz[v]=1;
pii pi=get_dist(v,d);
if(z[D-pi.ff])
o=min(o,pi.ss+z[D-pi.ff]);
for(auto& i:a[v]){
if(i.ff!=u && !mark[i.ff]){
dfs2(i.ff,v,d);
siz[v]+=siz[i.ff];
}
}
}
void dfs3(int v,int u,int d){
pii pi=get_dist(v,d);
z[D-pi.ff]=pi.ss;
for(auto& i:a[v])
if(i.ff!=u && !mark[i.ff])
dfs3(i.ff,v,d);
}
int centroid(int v,int u,int x){
for(auto& i:a[v]){
if(!mark[i.ff] && i.ff!=u && siz[i.ff]*2>siz[x])
return centroid(i.ff,v,u);
}
return v;
}
void centroid_decomposition(int v){
int o=centroid(v,-1,v);
mark[o]=1;
for(auto& i:a[o]){
if(!mark[i.ff]){
dfs2(i.ff,-1,o);
dfs3(i.ff,-1,o);
}
}
z.clear();
for(auto& i:a[o])
if(!mark[i.ff])
centroid_decomposition(i.ff);
}
void dfs(int v,int u){
par[v][0]=u;
for(auto& i:a[v]){
if(i.ff==u) continue;
dpt[i.ff]=dpt[v]+1;
dept[i.ff]=dept[v]+i.ss;
dfs(i.ff,v);
}
}
int best_path(int n,int x,int e[MAXN][2],int l[MAXN]){
o=n;
D=x;
int p,q,r;
for(int i=0;i<n;i++){
a[e[i][0]].append({e[i][1],l[i]});
a[e[i][1]].append({e[i][0],l[i]});
}
for(int i=pwr[0]=1;i<18;i++)
pwr[i]=pwr[i-1]*2;
dept[0]=0;
dfs(0,-1);
for(int i=0;i<18;i++)
par[0][i]=-1;
for(int j=0;j<17;j++)
for(int i=1;i<n;i++)
par[i][j+1]=par[max(par[i][j],0)][j];
for(int i=0;i<n;i++){
p=i;
q=0;
for(int j=17;j>=0;j--){
if(par[p][j]<0) continue;
else if(dept[i]-dept[par[p][j]]<=x){
p=par[p][j];
q+=pwr[j];
if(dept[i]-dept[p]==x) o=min(o,q);
}
}
}
dfs2(0,-1,0);
z.clear();
centroid_decomposition(0);
if(o==n) return -1;
return o;
}
