#include "race.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
vector<vector<pair<int,int>>> neigh;
vector<vector<int>> child;
vector<int> parent;
vector<int> ta;
vector<int> childC;
vector<int> hide;
vector<int> cindx;
vector<int> dep;
unordered_set<int> tch;
int n;
int K;
int ct=0;
int _n=0;
int build_tree(int x, int p){
childC[x]=1;
for (int t=0; t<sz(neigh[x]); t++)
{
int u=neigh[x][t].first;
if(u==p||cindx[u]>=0) continue;
childC[x]+=build_tree(u,x);
}
return childC[x];
}
int centroid(int x, int p){
for (int t=0; t<sz(neigh[x]); t++)
{
int u=neigh[x][t].first;
if(u==p||cindx[u]>=0) continue;
if(childC[u]*2>=_n) return centroid(u,x);
}
return x;
}
void calk(int x, int d, int d2, int mn, int p){
if(d>K) return;
dep[d]=min(d2,dep[d]);
tch.insert(d);
for (auto u : neigh[x])
{
if(u.first==p||mn>=cindx[u.first]) continue;
calk(u.first, d+u.second, d2+1, mn, x);
}
return;
}
vector<pair<pair<int,int>,pair<int,int>>> cmp;
vector<vector<pair<int,int>>> al;
int dfs(int x, int p){
int mx=0;
for (int t=0; t<sz(neigh[x]); t++)
{
if(cindx[neigh[x][t].first]<=cindx[x]) continue;
tch.clear();
calk(neigh[x][t].first,neigh[x][t].second,1,cindx[x],x);
for (auto u: tch)
{
al[t].push_back({u,dep[u]});
if(cmp[u].first.first==0) cmp[u].first={t+1,al[t].back().second};
else if(cmp[u].second.first==0) cmp[u].second={t+1,al[t].back().second};
else{
if(cmp[u].first.second>dep[u]) cmp[u].first={t+1,al[t].back().second};
else if(cmp[u].second.second>dep[u]) cmp[u].second={t+1,al[t].back().second};
}
tch.erase(u);
dep[u]=1e9;
}
}
int mn=1e9;
for (int t=0; t<sz(neigh[x]); t++){
for (int j=0; j<sz(al[t]); j++)
{
int d=al[t][j].first; int v=al[t][j].second;
int nd=K-d;
int v2=1e9;
if(nd==0){
mn=min(v,mn);
continue;
}
if(cmp[nd].first.first==0) continue;
else{
if(cmp[nd].first.first==t+1){
if(cmp[nd].second.first==0) continue;
else v2=cmp[nd].second.second;
}else v2=cmp[nd].first.second;
}
mn=min(v+v2,mn);
}
}
for (int t=0; t<sz(neigh[x]); t++){
for (int j=0; j<sz(al[t]); j++)
{
int d=al[t][j].first;
cmp[d]={{0,0},{0,0}};
}
}
for (auto u : neigh[x])
{
if(u.first==p) continue;
mn=min(mn,dfs(u.first, x));
}
return mn;
}
void decompo(int x, int compoINDEX){
build_tree(x,-1);
_n=childC[x];
int c=centroid(x,-1);
cindx[c]=compoINDEX;
for (auto u : neigh[c])
{
if(cindx[u.first]>=0) continue;
decompo(u.first,compoINDEX+1);
}
}
int best_path(int N, int _K, int H[][2], int L[])
{
K=_K;
n=N;
neigh.resize(n);
cindx.resize(n);
al.resize(n);
dep.resize(K+1,1e9);
cmp.resize(K+1,{{0,0},{0,0}});
childC.resize(n,0);
for (int i = 0; i < n-1; i++)
{
int a=H[i][0],b=H[i][1];
neigh[a].push_back({b,L[i]});
neigh[b].push_back({a,L[i]});
}
cindx.clear(); cindx.resize(n,-1);
childC.resize(n);
decompo(0,0);
for (int i = 0; i < n; i++)
{
if(cindx[i]<0) cindx[i]=1e5;
}
int res=dfs(0,-1);
if(res>n) return -1;
return res;
}
