#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int N=200005;
vector< pair<int,int> > adj[N];
vector<int> adjj[N];
long long sz[N],dp[N][20],par[N],hi[N],dis[N];
int del[N];
int nn;
long long anss=(1<<30);
void dfs(int x,int pa)
{
dp[x][0]=pa;
if(pa!=-1) hi[x]=hi[pa]+1;
else hi[x]=0;
for(int i=1;i<20;i++)
dp[x][i]=dp[dp[x][i-1]][i-1];
int cur=0;
for(auto it=adj[x].begin();it!=adj[x].end();it++)
{
if((*it).first != pa) {dis[(*it).first]=dis[x]+(*it).second; dfs((*it).first,x); cur++;}
}
}
void dfs2(int x,int pa)
{
sz[x]=1;
nn++;
for(auto it=adj[x].begin();it!=adj[x].end();it++)
{
if((*it).first == pa || del[(*it).first]) continue;
dfs2((*it).first,x);
sz[x]+=sz[(*it).first];
}
}
int getcentroid(int x,int pa)
{
for(auto it=adj[x].begin();it!=adj[x].end();it++)
{
if((*it).first == pa || del[(*it).first]) continue;
if(sz[(*it).first]>nn/2)
return getcentroid((*it).first,x);
}
return x;
}
int lca(int x,int y)
{
if(hi[x]<hi[y]) swap(x,y);
for(int i=19;i>=0;i--)
if(hi[x]-(1<<i)>=hi[y])
x=dp[x][i];
if(x==y) return x;
for(int i=19;i>=0;i--)
{
if(dp[x][i]!=dp[y][i])
{
x=dp[x][i]; y=dp[y][i];
}
}
return dp[x][0];
}
int gethi(int x,int y)
{
return hi[x]+hi[y]-2*hi[lca(x,y)];
}
long long getdis(int x,int y)
{
return dis[x]+dis[y]-2*dis[lca(x,y)];
}
int ans[1000006];
void go(int x,int pa,int K,int root)
{
long long z=getdis(x,root);
if(z<=K)
anss=min(anss,1LL*ans[K-z]+gethi(x,root));
for(auto it=adj[x].begin();it!=adj[x].end();it++)
{
if((*it).first == pa || del[(*it).first]) continue;
go((*it).first,x,K,root);
}
if(z<=K)
ans[z]=min(ans[z],gethi(x,root));
}
void clear(int x,int pa,int K,int root)
{
long long z=getdis(x,root);
if(z<=K)
ans[K-z]=(1<<30);
for(auto it=adj[x].begin();it!=adj[x].end();it++)
{
if((*it).first == pa || del[(*it).first]) continue;
clear((*it).first,x,K,root);
}
if(z<=K)
ans[z]=(1<<30);
}
int maxil=0;
void decompose(int x,int pa,int K,int lev=0)
{
nn=0;
dfs2(x,-1);
int centroid=getcentroid(x,-1);
//cout << x << " " << centroid << " " << nn << endl;
if(pa==-1) pa=centroid;
par[centroid]=pa;
clear(centroid,-1,K,centroid);
ans[0]=0;
go(centroid,-1,K,centroid);
del[centroid]=1;
maxil=max(maxil,lev);
for(auto it=adj[centroid].begin();it!=adj[centroid].end();it++)
{
if(del[(*it).first]) continue;
decompose((*it).first,centroid,K,lev+1);
}
}
int best_path(int N, int K, int H[][2], int L[]){
for(int i=0;i<N-1;i++)
{
int x=H[i][0],y=H[i][1],l=L[i];
adj[x].push_back({y,l});
adjj[x].push_back(y);
adj[y].push_back({x,l});
adjj[y].push_back(x);
}
dfs(0,-1);
decompose(0,-1,K);
//cout << gethi(90,74-12) << " " << gethi(90,74)+gethi(74,74-12) << endl;
/*for(int i=0;i<N;i++)
{
int x=i;
cout << x << ": \n";
while(1)
{
long long aa=getdis(x,i),bb=gethi(x,i);
if(ans[x].find(K-aa)!=ans[x].end())
{
anss=min(anss,bb+ans[x][K-aa]);
if(bb+ans[x][K-aa]==28)
{
cout << i << " " << x << " " << ans[x][K-aa] << endl;
}
}
if(aa<=K){
long long z=(ans[x].find(aa)==ans[x].end()?(1<<30):ans[x][aa]);
ans[x][aa]=min(z,bb);
}
if(bb==12)
{
cout << i << " " << x << " " << aa << " " << bb << " :HERE " << endl;
}
if(x==par[x]) break;
x=par[x];
cout << x << endl;
}
}*/
return (anss==(1<<30)?-1:anss);
}
