#include "race.h"
#include <bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
long long int typedef li;
vector<vector<pair<int,int>>> g(200005);
int ch[200005],ans=1e9;
struct offmap
{
map<li,int> mapa;
li key_offset=0;
int value_offset=0;
void add(int x, int k)
{
auto it=mapa.find(x-key_offset);
if (it==mapa.end()) mapa[x-key_offset]=k-value_offset;
else it->yy=min(it->yy,k-value_offset);
}
int find(int x)
{
auto it=mapa.find(x-key_offset);
if (it==mapa.end()) return 1e9;
return it->yy+value_offset;
}
void uproot(int w)
{
key_offset+=w;
value_offset++;
}
vector<pair<int,int>> iter()
{
vector<pair<int,int>> ret;
for (auto it : mapa) ret.push_back({it.xx+key_offset,it.yy+value_offset});
return ret;
}
} dub[200005];
int gde[200005];
int K;
void dfs(int p, int q)
{
gde[p]=p;
for (auto [it,w] : g[p]) if (it!=q)
{
dfs(it,p);
if (ch[gde[it]]>ch[gde[p]]) gde[p]=gde[it];
ch[p]+=ch[it];
}
for (auto [it,w] : g[p]) if (it!=q) dub[gde[it]].uproot(w);
dub[gde[p]].add(0,0);
for (auto [it,w] : g[p]) if (it!=q && it!=gde[p])
{
vector<pair<int,int>> tmp=dub[gde[it]].iter();
for (auto it : tmp) ans=min(ans,it.yy+dub[gde[p]].find(K-it.xx));
for (auto it : tmp) dub[gde[p]].add(it.xx,it.yy);
}
ans=min(ans,dub[gde[p]].find(K));
/*cout<<p<<": "<<endl;
vector<pair<int,int>> tmp=dub[gde[p]].iter();
for (auto it : tmp) cout<<it.xx<<": "<<it.yy<<endl;
cout<<endl;*/
}
int best_path(int n, int k, int H[][2], int L[])
{
for (int i=0;i<n-1;i++) g[H[i][0]].push_back({H[i][1],L[i]}),g[H[i][1]].push_back({H[i][0],L[i]});
for (int i=0;i<n;i++) ch[i]=1;
K=k,dfs(0,-1); return (ans==1e9?-1:ans);
}
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/
