#include "race.h"
#include <iostream>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 300001;
vector<pair<int,ll> > tree[MAXN];
int sz[MAXN],kill[MAXN];
void addEdge(int u,int v,ll w){
tree[u].push_back(make_pair(v,w));
tree[v].push_back(make_pair(u,w));
}
void dfs(int here,int dad){
sz[here] = 1;
for(int i=0;i<tree[here].size();i++){
int there = tree[here][i].first;
if(there == dad || kill[there]) continue;
dfs(there,here);
sz[here] += sz[there];
}
}
int getCenter(int here,int dad,int cap){
for(int i=0;i<tree[here].size();i++){
int there = tree[here][i].first;
if(there == dad || kill[there]) continue;
if(sz[there] > cap) return getCenter(there,here,cap);
}
return here;
}
void dfs2(int here,int dad,ll dep,map<ll,ll> &tcnt,int d){
if(tcnt.find(dep) == tcnt.end()) tcnt[dep] = d;
else{ tcnt[dep] = min(tcnt[dep],1LL * d); }
for(int i=0;i<tree[here].size();i++){
int there = tree[here][i].first;
ll w = tree[here][i].second;
if(there == dad || kill[there]) continue;
dfs2(there,here,dep+w,tcnt,d+1);
}
}
long long ans;
void decompose(int root,ll K){
dfs(root,-1);
int center = getCenter(root,-1,sz[root]/2);
map<ll,ll> cnt;
cnt[0] = 0;
for(int i=0;i<tree[center].size();i++){
int there = tree[center][i].first;
ll w = tree[center][i].second;
if(kill[there]) continue;
map<ll,ll> tcnt;
dfs2(there,center,w,tcnt,1);
for(auto it = tcnt.begin(); it!= tcnt.end(); it++){
ll need = K - it->first;
if(cnt.find(need) != cnt.end()) ans = min(ans,it->second + cnt[need]);
}
for(auto it = tcnt.begin(); it!= tcnt.end(); it++){
if(cnt.find(it->first) == cnt.end()) cnt[it->first] = it->second;
else{ cnt[it->first] = min(cnt[it->first],it->second); }
}
}
kill[center] = 1;
for(int i=0;i<tree[center].size();i++){
int there = tree[center][i].first;
if(kill[there]) continue;
decompose(there,K);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
ans = 4e18;
for(int i=0;i<N-1;i++){
addEdge(H[i][0],H[i][1],L[i]);
}
decompose(0,K);
if(ans == 4e18) ans = -1;
return (int)ans;
}
