#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
int vis[200001]={},vis1[200001]={},sz[200001],vis2[200001];
map<int,int> m[200001];
vector<ii> al[200001];
int n,k,ans=200001,co=0;
void dfs(int node)
{
vis1[node]=1;
//cout<<node<<endl;
sz[node]=1;
for(int i=0;i<al[node].size();++i)
{
if(vis[al[node][i].F]+vis1[al[node][i].F]==0)
{
dfs(al[node][i].F);
sz[node]+=sz[al[node][i].F];
}
}
}
int tell(int node,int p,int to)
{
for(int i=0;i<al[node].size();++i)
if(vis[al[node][i].F]==0&&al[node][i].F!=p&&sz[al[node][i].F]>to/2)
return(tell(al[node][i].F,node,to));
return(node);
}
void dfs1(int node,int root,int upa,int dis,int e)
{
vis2[node]=1;
if(upa!=-1)
{
if(m[upa].find(dis)==m[upa].end())
m[upa][dis]=e;
else
m[upa][dis]=min(m[upa][dis],e);
}
int f=-1;
for(int i=0;i<al[node].size();++i)
{
if(vis[al[node][i].F]+vis2[al[node][i].F]==0)
{
if(root==node)
{
f=al[node][i].F;
dfs1(al[node][i].F,root,al[node][i].F,dis+al[node][i].S,e+1);
m[al[node][i].F][0]=0;
}
else
dfs1(al[node][i].F,root,upa,dis+al[node][i].S,e+1);
}
}
if(node==root)
{
for(int i=0;i<al[node].size();++i)
{
// cout<<f<<' '<<al[node][i].F<<endl;
if(f==al[node][i].F||vis[al[node][i].F]==1)
continue;
for(auto j=(m[al[node][i].F].begin());j!=m[al[node][i].F].end();++j)
{
if((*j).F>k)
break;
if(m[f].find(k-(*j).F)!=m[f].end())
ans=min(ans,m[f][k-(*j).F]+(*j).S);
}
for(auto j=(m[al[node][i].F].begin());j!=m[al[node][i].F].end();++j)
{
if(m[f].find((*j).F)==m[f].end())
m[f][(*j).F]=(*j).S;
else
m[f][(*j).F]=min(m[f][(*j).F],(*j).S);
}
m[al[node][i].F].clear();
}
if(f!=-1)
m[f].clear();
}
}
int best_path(int N, int K, int H[][2], int L[])
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
n=N;
k=K;
int c=0;
for(int i=0;i<n-1;++i)
{
al[H[i][0]].pb(mp(H[i][1],L[i]));
al[H[i][1]].pb(mp(H[i][0],L[i]));
}
while(c!=n)
{
for(int i=0;i<n;++i)
{
if(vis[i]+vis1[i]==0)
{
// cout<<"hi "<<i<<' '<<vis1[i]<<endl;
dfs(i);
int cen=tell(i,i,sz[i]);
vis[cen]=1;
//cout<<i<<cen<<endl;
dfs1(cen,cen,-1,0,0);
c++;
}
}
// cout<<ans<<"Masti"<<endl;
memset(vis1,0,sizeof(vis1));
memset(vis2,0,sizeof(vis2));
}
if(ans==200001)
return(-1);
return(ans);
}
