#include "race.h"
#include <vector>
#include <algorithm>
#include <set>
#define N 200001
#define M 1000001
#define INF 999999999
#define min2(x,y) (x<y?x:y)
using namespace std;
int n, m, out=INF;
vector<pair<int, long long> > r[N];
set<int> prohibit[N];
int len, core, d_cnt[N];
pair<int,int> d[M];
bool check[N];
bool check_can(int x, int y) {
set<int>::iterator it = prohibit[x].lower_bound(y);
if (it == prohibit[x].end() || *it != y) return true;
return false;
}
void find_len(int x) {
check[x] = true, len++;
for (auto i : r[x])
if (check[i.first] == false && check_can(x, i.first)) find_len(i.first);
}
int find_cnt(int x, int up) {
d_cnt[x] = 1, check[x] = false;
for (auto i : r[x])
if (i.first != up && check_can(x, i.first)) d_cnt[x] += find_cnt(i.first, x);
return d_cnt[x];
}
void find_core(int x, int up, int up_cnt) {
bool core_check = true;
if (up_cnt > len / 2) return;
for(auto i:r[x])
if (i.first != up && check_can(x, i.first)) {
if (d_cnt[i.first] > len / 2) core_check = false;
find_core(i.first, x, up_cnt + d_cnt[x] - d_cnt[i.first]);
}
if (core_check) core = x;
}
void Update(int x, int up, int tot_len, int cnt) {
if (tot_len > m) return;
if (d[m - tot_len].first == core) out = min2(out, cnt + d[m - tot_len].second);
for (auto i : r[x])
if (i.first != up && check_can(x, i.first)) Update(i.first, x, tot_len + i.second, cnt + 1);
}
void Push(int x, int up, int tot_len, int cnt) {
if (tot_len > m) return;
if (d[tot_len].first != core) d[tot_len] = { core,cnt };
else if (d[tot_len].second > cnt) d[tot_len] = { core,cnt };
for (auto i : r[x])
if (i.first != up && check_can(x, i.first)) Push(i.first, x, tot_len + i.second, cnt + 1);
}
void f(int start) {
len = 0, find_len(start);
find_cnt(start, 0), find_core(start, 0, 0);
d[0] = { core,0 };
for (auto i : r[core])
if (check_can(core, i.first)) {
Update(i.first, core, i.second, 1);
Push(i.first, core, i.second, 1);
}
int _core = core;
for (auto i : r[_core])
if (check_can(_core, i.first)) {
prohibit[_core].insert(i.first);
prohibit[i.first].insert(_core);
f(i.first);
}
}
int best_path(int _n, int _m, int in1[][2], int in2[]) {
n = _n, m = _m;
for (int i = 0; i < n - 1; i++) {
int x = in1[i][0] + 1, y = in1[i][1] + 1;
r[x].push_back({ y,in2[i] });
r[y].push_back({ x,in2[i] });
}
f(1);
return out == INF ? -1 : out;
}
