#include "race.h"
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <iomanip>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <map>
#define ll long long
#define X first
#define Y second
using namespace std;
int n, k;
const int MAXN = 200010;
vector<pair<int,int>> v[MAXN];
int par[MAXN];
map<int, int> m[MAXN];
int ans=MAXN;
int depth[MAXN],depthlen[MAXN];
void dfs1(int beg,int par)
{
for(auto nb:v[beg])
{
if(nb.X==par)continue;
depth[nb.X]=depth[beg]+1;
depthlen[nb.X]=depthlen[beg]+nb.Y;
dfs1(nb.X,beg);
}
}
int findpar(int x)
{
if(par[x]==x)return x;
return par[x]=findpar(par[x]);
}
void join(int a,int b,int lca)
{
a=findpar(a);
b=findpar(b);
if(a==b)return;
if(m[b].size()>m[a].size())m[a].swap(m[b]);
for(auto [key,value] : m[b])
{
if(value==0)continue;
int third=k-key+2*depthlen[lca];
int anss=m[a][third];
if(anss==0)continue;
ans=min(ans,anss+value-2*depth[lca]);
}
for(auto [key,value] : m[b])
{
if(value==0)continue;
if(m[a][key]==0 || m[a][key]>value)m[a][key]=value;
}
par[b]=a;
}
void dfs2(int beg,int par)
{
for(auto nb:v[beg])
{
if(nb.X==par)continue;
dfs2(nb.X,beg);
join(beg,nb.X,beg);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
for (int i = 0; i < n-1; i++)
{
v[H[i][0]+1].push_back({H[i][1]+1,L[i]});
v[H[i][1]+1].push_back({H[i][0]+1,L[i]});
}
depth[1]=0;
depthlen[1]=0;
dfs1(1,1);
for(int i=1;i<=n;i++)
{
//cout<<i<<' '<<depth[i]<<" "<<depthlen[i]<<endl;
par[i]=i;
m[i][depthlen[i]]=depth[i];
}
dfs2(1,1);
if(ans==MAXN)ans=-1;
return ans;
}
