#include "race.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;
bool mk[200010];
int n,k;
vii adj[200010];
int sub[200010];
int ans = 1e9, cnt;
int subsize(int v, int par)
{
int sum = 0;
for(int i = 0; i < adj[v].size(); i++)
if(adj[v][i].first != par && !mk[adj[v][i].first])
sum += subsize(adj[v][i].first,v);
sub[v] = sum + 1;
return sum + 1;
}
int centroid(int v, int par, int sz)
{
for(int i = 0; i < adj[v].size(); i++)
if(adj[v][i].first != par && !mk[adj[v][i].first])
{
int u = adj[v][i].first;
if(sub[u] > sz/2)
return centroid(u,v,sz);
}
return v;
}
void dfs(int v, int par, int d, int len, map<int,int>& m)
{
if(len > k)
return;
if(m.find(len) != m.end())
m[len] = min(m[len],d);
else
m[len] = d;
for(int i = 0; i < adj[v].size(); i++)
{
int u = adj[v][i].first;
int l = adj[v][i].second;
if(u != par && !mk[u])
dfs(u,v,d+1,len + l, m);
}
}
void solveForCen(int v)
{
map<int,int> mp;
mp[0] = 0;
for(int i = 0;i < adj[v].size(); i++)
{
if(!mk[adj[v][i].first])
{
map<int,int> m;
int u = adj[v][i].first;
dfs(u,v,1,adj[v][i].second,m);
for(map<int,int>::iterator it = m.begin(); it != m.end(); it++)
{
int len = it->first;
if(mp.find(k - len) != mp.end())
ans = min(ans,m[len] + mp[k - len]);
}
for(map<int,int>::iterator it = m.begin(); it != m.end(); it++)
{
int len = it->first;
if(mp.find(len) != mp.end())
mp[len] = min(mp[len],m[len]);
else
mp[len] = m[len];
}
}
}
}
int solve(int v)
{
subsize(v,v);
int cen = centroid(v,v,sub[v]);
mk[cen] = true;
solveForCen(cen);
for(int i = 0; i < adj[cen].size(); i++)
{
int u = adj[cen][i].first;
if(!mk[u])
solve(u);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
for(int i = 0; i < N -1; i++)
{
int v = H[i][0],u = H[i][1],l = L[i];
adj[v].pb(ii(u,l));
adj[u].pb(ii(v,l));
}
solve(0);
if(ans == 1e9)
return -1;
else
return ans;
}
