#include "race.h"
#include <bits/stdc++.h>
#include<unordered_map>
#define F first
#define S second
typedef long long ll;
using namespace std;
int n,k;
int ans=1000000000;
vector<pair<int,int> > v[200010];
bool blocked [200010];
int dep[1000010];
int P[200010];
//unordered_map<int,int> dep;
int Size[200010];
void dfsSize(int nod,int pt){
Size[nod]=1;
P[nod]=pt;
// cout <<"=============== "<<nod<<endl;
for (int i=0;i<v[nod].size();i++){
if (v[nod][i].F==pt||blocked[v[nod][i].F])continue;
dfsSize(v[nod][i].F,nod);
Size[nod]+=Size[v[nod][i].F];
}
}
vector<pair<int,int> > comp;
int dfsAdd (int nod,int pt,int d,int d1){
if (d>k)return 1000000000;
//dep[d]=min(dep[d],d1);
int res=dep[k-d]+d1;
comp.push_back({d,d1});
for (int i=0;i<v[nod].size();i++){
if (v[nod][i].F==pt||blocked[v[nod][i].F])continue;
res=min(res,dfsAdd(v[nod][i].F,nod,d+v[nod][i].S,d1+1));
}
return res;
}
void dfsRem(int nod,int pt,int d){
if (d>k)return;
dep[d]=1000000000;
for (int i=0;i<v[nod].size();i++){
if (v[nod][i].F==pt||blocked[v[nod][i].F])continue;
dfsRem(v[nod][i].F,nod,d+v[nod][i].S);
}
}
int rrr=0;
int Solve (int nod){
rrr++;
if (rrr>n)assert(0);
//cout <<nod<<" -------------\n";
dep[0]=0;
int res=1000000000;
for (int i=0;i<v[nod].size();i++){
if (blocked[v[nod][i].F])continue;
res=min(res,dfsAdd(v[nod][i].F,nod,v[nod][i].S,1));
pair<int,int>qwe;
while (comp.size()>0){
qwe=comp[comp.size()-1];
comp.pop_back();
int d=qwe.F;
int d1=qwe.S;
dep[d]=min(dep[d],d1);
}
//res=min(res,dfsCount(v[nod][i].F,nod,v[nod][i].S,1));
}
dfsRem (nod,-1,0);
return res;
}
int rr;
void Create (int nod0){
rr++;
if (rr>n)assert(0);
//if (vis[nod0]>)return;
//vis[nod0]=1;
//cout <<nod0<<" asdf\n";
dfsSize(nod0,-1);
pair<int,int> cen={Size[nod0],nod0};
//for (int i=0;i<n;i++){
//cout <<Size[i]<<" ";
//}cout <<endl;
int centroid=nod0,mn=1e9;
int nod=nod0,curmx=0;
while (1){
int z=0;
for (int i=0;i<v[nod].size();i++){
if (blocked[v[nod][i].F])continue;
if (v[nod][i].F==P[nod]){
if (curmx<Size[nod0]-Size[nod])z=v[nod][i].F;
curmx=max(curmx,Size[nod0]-Size[nod]);
continue;
}
if (curmx<Size[v[nod][i].F])z=v[nod][i].F;
curmx=max(curmx,Size[v[nod][i].F]);
}
if (curmx<mn){
mn=curmx;
centroid=nod;
nod=z;
curmx=0;
}else break;
}
cen.S=centroid;
//if (blocked[cen.S])return;
//cout <<cen.S<<endl;
blocked[cen.S]=true;
ans=min(Solve(cen.S),ans);
for (int i=0;i<v[cen.S].size();i++){
if (blocked[v[cen.S][i].F])continue;
Create(v[cen.S][i].F);
}
}
int best_path(int N, int K, int H[][2], int L[]){
n=N;k=K;
//if (n<80000||n>100000)return 0;
//if (K<)return 0;
for (int i=0;i<=K;i++){
dep[i]=1000000000;
}
for (int i=0;i<n-1;i++){
int x=H[i][0];
int y=H[i][1];
//cout <<x<<" - "<<y<<endl;
v[x].push_back({y,L[i]});
v[y].push_back({x,L[i]});
}
Create (0);
if (ans==1000000000)return -1;
return ans;
}
