#include <bits/stdc++.h>
using namespace std;
template<typename TH>
void _dbg(const char* sdbg, TH h)
{
cerr << sdbg << " = " << h << "\n";
}
template<typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t)
{
while (*sdbg != ',') cerr << *sdbg++;
cerr << " = " << h << ",";
_dbg(sdbg + 1, t...);
}
#define db(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define chkpt cerr << "--- Checkpoint here ---\n";
const int N=2e5+5,K=1e6+6,INF=1e9,LOG_N=20;
struct Edge{
int u,v,w;
int Adj(int x){
return u^v^x;
}
};
int n,k;
Edge edgeList[N];
vector<int> g[N],ct[N];
int h[LOG_N][2*N],idx[N],tin[N],tme,st[N],d[N];
vector<int> events;
int64_t s[N];
bool del[N];
int sz[N],ans=INF,f[K];
void DFS_LCA(int u,int fa){
idx[tin[u]=tme++]=u;
st[u]=events.size();
events.push_back(tin[u]);
for(int id:g[u]){
int v=edgeList[id].Adj(u),w=edgeList[id].w;
if(v!=fa){
d[v]=d[u]+1;
s[v]=s[u]+w;
DFS_LCA(v,u);
events.push_back(tin[u]);
}
}
}
void BuildLCA(){
DFS_LCA(1,-1);
for(int i=0;i<events.size();++i){
h[0][i]=events[i];
}
for(int i=1;i<LOG_N;++i){
for(int j=1;j+(1<<i-1)<events.size();++j){
h[i][j]=min(h[i-1][j],h[i-1][j+(1<<i-1)]);
}
}
}
int Query(int u,int v){
int l=u==v?0:__lg(v-u);
return min(h[l][u],h[l][v-(1<<l)+1]);
}
int LCA(int u,int v){
if(st[u]>st[v]){
swap(u,v);
}
return idx[Query(st[u],st[v])];
}
int EdgeDist(int u,int v){
return d[u]+d[v]-2*d[LCA(u,v)];
}
int64_t WeightDist(int u,int v){
return s[u]+s[v]-2*s[LCA(u,v)];
}
void DFS_Size(int u,int fa){
sz[u]=1;
for(int id:g[u]){
int v=edgeList[id].Adj(u);
if(v!=fa&&!del[v]){
DFS_Size(v,u);
sz[u]+=sz[v];
}
}
}
int FindCentroid(int u,int fa,int curSz){
int maxSize=0,big=0;
for(int id:g[u]){
int v=edgeList[id].Adj(u);
if(v!=fa&&!del[v]&&sz[v]>maxSize){
maxSize=sz[v];
big=v;
}
}
if(maxSize<=curSz/2){
return u;
}
return FindCentroid(big,u,curSz);
}
int BuildCentroidTree(int u){
DFS_Size(u,-1);
int cen=FindCentroid(u,-1,sz[u]);
del[cen]=true;
for(int id:g[cen]){
int v=edgeList[id].Adj(cen);
if(!del[v]){
int tmp=BuildCentroidTree(v);
ct[cen].push_back(tmp);
// cout<<cen<<' '<<tmp<<'\n';
}
}
return cen;
}
void DFS_Reset(int u,int r){
int64_t id=WeightDist(u,r);
if(id<K){
f[id]=INF;
}
for(int v:ct[u]){
DFS_Reset(v,r);
}
}
void DFS_UpdateAns(int u,int r){
int64_t id=WeightDist(u,r);
if(id<=k&&f[k-id]!=INF){
ans=min(ans,EdgeDist(u,r)+f[k-id]);
}
for(int v:ct[u]){
DFS_UpdateAns(v,r);
}
}
void DFS_UpdateF(int u,int r){
int64_t id=WeightDist(u,r);
if(id<=k){
f[id]=min(f[id],EdgeDist(u,r));
}
for(int v:ct[u]){
DFS_UpdateF(v,r);
}
}
void Calc(int u){
for(int v:ct[u]){
f[0]=0;
DFS_UpdateAns(v,u);
DFS_UpdateF(v,u);
}
DFS_Reset(u,u);
}
int Solve(){
BuildLCA();
BuildCentroidTree(1);
for(int i=0;i<K;++i){
f[i]=INF;
}
for(int i=1;i<=n;++i){
Calc(i);
}
return ans==INF?-1:ans;
}
int best_path(int N,int K,int H[][2],int L[])
{
n=N;
k=K;
for(int i=0;i<=n-2;++i){
int u=H[i][0]+1,v=H[i][1]+1;
g[u].push_back(i+1);
g[v].push_back(i+1);
edgeList[i+1]={u,v,0};
}
for(int i=0;i<=n-2;++i){
edgeList[i+1].w=L[i];
}
return Solve();
}
//int main()
//{
//// freopen("IOI11_race.inp","r",stdin);
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cin>>n>>k;
// for(int i=1;i<=n-1;++i){
// int u,v,w;
// cin>>u>>v>>w;
// u++;
// v++;
//// cout<<u<<' '<<v<<'\n';
// g[u].push_back(i);
// g[v].push_back(i);
// edgeList[i]={u,v,w};
// }
//// for(int i=1;i<=n-1;++i){
//// cin>>edgeList[i].w;
//// }
// cout<<Solve();
// return 0;
//}
