#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
typedef int64_t lld;
typedef pair<int, int> pii;
/*
struct node;
vector<node*> nodes;
struct node{
node *L = 0, *R = 0;
lld l, r, mid;
int val = 0;
node(lld ll, lld rr) : l(ll), r(rr), mid((l+r)/2) {}
node(*node n){ L = n->L, R = n->R, l = n->l, r = n->r, mid = n->mid, val = n->val + 1; }
node* update(lld x){
node* n = new node(this);
if(l == r)return n;
if(x <= mid){
if(!n->L) n->L = new node(l, mid);
return n->L->update(x);
}else{
if(!n->R) n->R = new node(mid+1, r);
return n->R->update(x);
}
}
};
*/
vector<vector<pii>> G;
int getSize(int i, int p){
int sz = 1;
for(auto x: G[i])if(x.ff != p)sz += getSize(x.ff, i);
return sz;
}
int getCent(int i, int p, int n){
int sz = 1; bool fl = true;
for(auto x : G[i])
if(x.ff != p){
auto r = getCent(x.ff, i, n);
if(r >= 0)return r;
r = -r;
if(r > n/2)fl = false;
sz += r;
}
if(n-sz > n/2)fl = false;
if(fl)return i;
else return -sz;
}
map<int, int> deps, tdeps;
void dfs(int i, int p, int d, int c){
if(!deps[d])deps[d] = c;
else deps[d] = min(deps[d], c);
for(auto x : G[i])
if(x.ff != p)
dfs(x.ff, i, d+x.ss, c+1);
}
int process(int r, int targ){
//cout << r << endl;
deps.clear(); tdeps.clear(); tdeps[0] = 1;
int ans = INT_MAX;
for(auto x: G[r]){
G[x.ff].erase(remove(all(G[x.ff]), make_pair(r, x.ss)), G[x.ff].end());
dfs(x.ff, r, x.ss, 2);
for(auto i: deps)
if(tdeps.find(targ-i.ff) != tdeps.end())
ans = min(ans, tdeps[targ-i.ff]+i.ss-1);
for(auto i: deps)
if(!tdeps[i.ff])tdeps[i.ff] = i.ss;
else tdeps[i.ff] = min(tdeps[i.ff], i.ss);
deps.clear();
}
G[r].resize(0);
return ans;
}
int best_path(int N, int K, int H[][2], int L[]) {
G.resize(N);
for(int i = 0; i < N-1; i++)G[H[i][0]].pb({H[i][1], L[i]}), G[H[i][1]].pb({H[i][0], L[i]});
int ans = INT_MAX;
for(int i = 0; i < N; i++)while(G[i].size())ans = min(ans, process(getCent(i, i, getSize(i, i)), K));
return ans == INT_MAX?-1:(ans-1);
}
