//#include "race.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge
{
int to;
ll w;
};
vector<edge> adjList[200005];
int Size[200005];
int getSize(int u,int p)
{
Size[u]=1;
for(edge e: adjList[u]){
int v=e.to;
if(v==p) continue;
Size[u]+=getSize(v,u);
}
return Size[u];
}
ll k;
ll minimum=INT_MAX;
map<ll,int>* sack[200005];
typedef pair<ll,int> pii;
void dfs(int u,int p,ll distRoot,int depth)
{
//cout<<u<<" "<<p<<" "<<distRoot<<" "<<depth<<endl;
int greatest=0,bigChild=-1;
for(edge e: adjList[u]){
int v=e.to;
if(v==p) continue;
//cout<<"V"<<v<<endl;
dfs(v,u,distRoot+e.w,depth+1);
if(Size[v]>greatest){
greatest=Size[v];
bigChild=v;
}
}
if(bigChild==-1)
sack[u]=new map<ll,int>;
else
sack[u]=sack[bigChild];
for(edge e: adjList[u]){
int v=e.to;
if(v==p) continue;
if(v==bigChild) continue;
for(pii x: *sack[v]){
ll dist=x.first-distRoot;
if((*sack[u]).find(k-dist+distRoot)!=(*sack[u]).end()){
ll length=(*sack[u])[k-dist+distRoot]+x.second;
length-=2*depth;
minimum=min(minimum,length);
}
if((*sack[u])[x.first]==0) (*sack[u])[x.first]=x.second;
else{
int length=(*sack[u])[x.first];
(*sack[u])[x.first]=min(length,x.second);
}
}
}
if((*sack[u]).find(k+distRoot)!=(*sack[u]).end()){
ll length=(*sack[u])[k+distRoot];
length-=depth;
minimum=min(minimum,length);
}
if((*sack[u])[distRoot]==0) (*sack[u])[distRoot]=depth;
else{
int length=(*sack[u])[distRoot];
(*sack[u])[distRoot]=min(length,depth);
}
//cout<<u<<" min"<<minimum<<endl;
//for(pii x: *sack[u]){
// cout<<x.first<<" "<<x.second<<endl;
//}
}
int best_path(int n, int K, int H[][2], int L[])
{
k=K;
for(int i=0;i<n-1;i++){
int a=H[i][0]+1;
int b=H[i][1]+1;
ll w=L[i];
adjList[a].push_back({b,w});
adjList[b].push_back({a,w});
}
/*for(int i=1;i<=n;i++){
cout<<i<<":";
for(edge e: adjList[i]){
cout<<e.to<<" ";
}
cout<<endl;
}*/
getSize(1,0);
dfs(1,0,0,0);
return (minimum!=INT_MAX)? minimum : -1;
}
