#include "race.h"
#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
//#include "race.h"
const int dydis = 2e5 + 10;
vector<pair<int, int> > gr[dydis];
int n, k;
bool vis[dydis] = {};
int tevas[dydis];
vector<int> visi;
int sz[dydis];
int ans = inf;
void dfs(int v, int came){
tevas[v] = came;
visi.push_back(v);
sz[v] = 1;
for(auto x : gr[v]){
if(x.first == came) continue;
dfs(x.first, v);
sz[v] += sz[x.first];
}
}
int findCentroid(int v){
visi.clear();
dfs(v, v);
for(auto x : visi){
int mx = 0;
int sm = 0;
for(int i = 0; i < (int)gr[x].size(); i++){
if(gr[x][i].first == tevas[x]) continue;
mx = max(mx, sz[gr[x][i].first]);
sm += sz[gr[x][i].first];
}
mx = max(mx, (int)visi.size()-sm-1);
if(mx <= (int)visi.size()/2+1) return x;
}
exit(0);
return -1;
}
int curAns[1000010];
int known[1000010];
vector<int> stt;
void dfs1(int v, int came, long long dst, int kek){
if(dst > k) return;
stt.push_back(dst);
curAns[dst] = min(curAns[dst], kek);
for(auto x : gr[v]){
if(x.first == came) continue;
dfs1(x.first, v, dst + x.second, kek+1);
}
}
void jeiPrik(int v){ // suskaiciuojam, koks ats, jei v priklauso atsakymui
known[0] = 0;
vector<int> lik;
for(auto x : gr[v]){
stt.clear();
dfs1(x.first, v, x.second, 1);
for(auto y : stt){
// cout << "bandau " << y << ", tai bus galimai " << curAns[y] << " + " << known[k-y] << endl;
ans = min(ans, curAns[y] + known[k-y]);
}
for(auto y : stt){
known[y] = min(known[y], curAns[y]);
}
for(auto x : stt) curAns[x] = inf;
for(auto x : stt) lik.push_back(x);
}
for(auto x : lik){
curAns[x] = known[x] = inf;
}
}
void calc(int v){
v = findCentroid(v);
jeiPrik(v);
// cout << "gaunam, kad centras yra " << v << endl;
vector<int> kaims;
for(auto x : gr[v]) kaims.push_back(x.first);
for(auto x : visi){
vector<pair<int, int> > naujas;
for(auto y : gr[x]){
if(y.first == v) continue;
naujas.push_back(y);
}
gr[x] = naujas;
}
// cout << "istrynem " << v << endl;
for(auto x : kaims) calc(x);
}
int best_path(int N, int K, int H[][2], int L[]){
for(int i = 0; i <= 1000000; i++) curAns[i] = known[i] = inf;
n = N; k = K;
for(int i = 0; i < n-1; i++){
gr[H[i][0]].push_back({H[i][1], L[i]});
gr[H[i][1]].push_back({H[i][0], L[i]});
}
calc(0);
return (ans == inf ? -1ll : ans);
}
/*
4 3
0 1 1
1 2 2
1 3 4
2
5 5
0 1 3
1 2 2
2 3 1
3 4 5
1
*/
