#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define fin cin
#define fout cout
//ifstream fin("x.in"); ofstream fout("x.out");
typedef long long i64;
const int nmax = 2e5;
static i64 K;
static int ans;
static int lant[nmax + 1], sz[nmax + 1];
static i64 ct[nmax + 1];
static vector<pair<int, int>> g[nmax + 1];
static set<pair<i64, int>> s[nmax + 1];
void dfs (int nod, int h, int dad = -1) {
sz[nod] = 1;
int mxf = -1, mxg = -1, valm = 0;
for (auto i : g[nod]) {
if (i.first != dad) {
dfs(i.first, h + 1, nod);
sz[nod] += sz[i.first];
if (sz[i.first] > mxg) {
mxg = sz[i.first];
mxf = i.first;
valm = i.second;
}
}
}
if (mxf == -1) {
lant[nod] = nod;
} else {
lant[nod] = lant[mxf];
}
ct[lant[nod]] += valm;
set<pair<i64, int>>::iterator it = s[lant[nod]].lower_bound({K - ct[lant[nod]], 0});
if (it != s[lant[nod]].end())
if ((it -> first) == K - ct[lant[nod]]) {
ans = min(ans, (it -> second) - h);
}
s[lant[nod]].insert({-ct[lant[nod]], h});
for (auto i : g[nod]) {
if (i.first == mxf || i.first == dad)
continue;
int l = lant[i.first];
ct[l] += i.second;
for (auto x : s[l]) {
it = s[lant[nod]].lower_bound({K - ct[lant[nod]] - x.first - ct[l], 0});
if (it != s[lant[nod]].end())
if ((it -> first) == K - ct[lant[nod]] - x.first - ct[l]) {
ans = min(ans, x.second + (it -> second) - 2 * h);
}
}
while (!s[l].empty()) {
pair<i64, int> x = *s[l].begin();
x.first += ct[l];
s[l].erase(s[l].begin());
s[lant[nod]].insert({x.first - ct[lant[nod]], x.second});
}
}
}
int best_path (int n, int k, int h[][2], int l[]) {
K = k;
for (int i = 0; i < n - 1; ++ i) {
g[h[i][0]].push_back({h[i][1], l[i]});
g[h[i][1]].push_back({h[i][0], l[i]});
}
ans = n + 1;
dfs(0, 0);
if (ans == n + 1)
ans = -1;
return ans;
}
/*int main() {
int a[11][2]= {0, 1,
0, 2,
2, 3,
3, 4,
4, 5,
0, 6,
6, 7,
6, 8,
8, 9,
8, 10};
int b[11] = {3,4,5,4,6,3,2,5,6,7};
//int a[3][2]= {0, 1, 1, 2, 1, 3 };
//int b[3] = {1, 2, 4};
cout << best_path (11, 12, a, b) << "\n";
return 0;
}*/
