// created by Dinh Manh Hung
// onepunchac168
// THPT CHUYEN HA TINH
// HA TINH, VIET NAM
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
//#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
//#pragma GCC target("sse4,avx2,fma")
#define task ""
#define ldb long double
#define pb push_back
#define fi first
#define se second
#define pc pop_back()
#define all(x) begin(x),end(x)
#define uniquev(v) v.resize(unique(all(v))-v.begin())
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define cntbit(v) __builtin_popcountll(v)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) ((1LL*a*b)/__gcd(a,b))
#define mask(x) (1LL<<(x))
#define readbit(x,i) ((x>>i)&1)
#define ins insert
typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;
ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};
const ldb PI = acos (-1);
//const ll mod=978846151;
//const ll base=29;
const int maxn=1e6+5;
const int mod=1e9+7;
const char nl = '\n';
ll n,k;
vector <ii> vt[200005];
ll res=1e9+5;
map <ll,ll> *mp[200005];
ll sz[200005];
ll sum[200005];
ll path[200005];
void dfsa(int u,int vv)
{
sz[u]=1;
for (auto v:vt[u])
{
if (v.fi==vv)
{
continue;
}
sum[v.fi]=sum[u]+v.se;
path[v.fi]=path[u]+1;
dfsa(v.fi,u);
sz[u]+=sz[v.fi];
}
}
void dfs(int u,int vv)
{
int bigchild=-1;
for (auto v:vt[u])
{
if (v.fi==vv)
{
continue;
}
if (bigchild==-1||sz[v.fi]>sz[bigchild])
{
bigchild=v.fi;
}
}
if (bigchild!=-1)
{
dfs(bigchild,u);
mp[u]=mp[bigchild];
}
else
{
mp[u]=new map <ll,ll>;
}
ll ss=sum[u]+k;
ll a1=(*mp[u])[ss];
if (a1!=0)
{
res=min(res,a1-path[u]);
}
ll aa=(*mp[u])[sum[u]];
if (sum[u]==k)
{
res=min(res,path[u]);
}
if (aa==0||path[u]<aa)
{
(*mp[u])[sum[u]]=path[u];
}
for (auto v:vt[u])
{
if (v.fi==vv||v.fi==bigchild)
{
continue;
}
dfs(v.fi,u);
for (auto cnt:*mp[v.fi])
{
ll aa=k+2*sum[u]-cnt.fi;
ll pp=(*mp[u])[aa];
if (pp!=0)
{
res=min(res,pp+cnt.se-2*path[u]);
}
}
for (auto cnt:*mp[v.fi])
{
ll aa=(*mp[u])[cnt.fi];
if (aa==0||cnt.se<aa)
{
(*mp[u])[cnt.fi]=cnt.se;
}
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n=N;
k=K;
for (int i=0;i<n-1;i++)
{
ll aa=H[i][0];
ll bb=H[i][1];
ll w=L[i];
vt[aa].pb({bb,w});
vt[bb].pb({aa,w});
}
sum[0]=0;
path[0]=1;
dfsa(0,-1);
dfs(0,-1);
if (res==1e9+5)
{
return -1;
}
return res;
}
