/////////////////////////////// _LeMur_
#define _CRT_SECURE_NO_WARNINGS
#include "race.h"
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <chrono>
#include <random>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
const int N = 200005;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
vector < pair<int, int> > g[N];
int answ = -1;
bool used[N];
int sz[N];
int nn = 0;
int k;
void dfs_sz(int v, int p) {
nn++;
sz[v] = 1;
for (int i = 0; i < (int)g[v].size(); i++) {
int to = g[v][i].first;
if (to == p) continue;
if (used[to]) continue;
dfs_sz(to, v);
sz[v] += sz[to];
}
}
int find_center(int v, int p) {
int mx_sz = -1, gag;
for (int i = 0; i < (int)g[v].size(); i++) {
int to = g[v][i].first;
if (to == p) continue;
if (used[to]) continue;
if (sz[to] > mx_sz) {
mx_sz = sz[to];
gag = to;
}
}
if (mx_sz * 2 <= nn) return v;
return find_center(gag, v);
}
int find_centroid(int v) {
nn = 0;
dfs_sz(v, -1);
int center = find_center(v, -1);
dfs_sz(center, -1);
return center;
}
vector < pair<int, int> > mas;
map <int, int> mp;
void update(int &answ, int x) {
if (answ == -1 || x < answ) {
answ = x;
}
}
void solve(int v, int p, int L, int r) {
if (p != -1) {
mas.push_back(make_pair(L, r));
}
for (int i = 0; i < (int)g[v].size(); i++) {
int to = g[v][i].first;
int len = g[v][i].second;
if (to == p || used[to]) continue;
solve(to, v, L + len, r + 1);
if (p == -1) {
for (int j = 0; j < (int)mas.size(); j++) {
int L = mas[j].first;
int d = mas[j].second;
if (L > k) continue;
if (L == k) {
update(answ, d);
} else {
if (mp.find(k - L) != mp.end()) {
update(answ, d + mp[k - L]);
}
}
}
for (int j = 0; j < (int)mas.size(); j++) {
int L = mas[j].first;
int d = mas[j].second;
if (L > k) continue;
if (mp.find(L) != mp.end()) {
mp[L] = min(mp[L], d);
} else {
mp[L] = d;
}
}
}
}
}
void centroid_decomposition() {
queue <int> q;
q.push(1);
while (!q.empty()) {
int v = q.front();
q.pop();
int center = find_centroid(v);
mp.clear();
solve(center, -1, 0, 0);
used[center] = true;
for (int i = 0; i < (int)g[center].size(); i++) {
int to = g[center][i].first;
if (used[to]) continue;
if (sz[to] == 1) continue;
q.push(to);
}
}
}
int best_path(int n, int K, int h[][2], int l[]) {
k = K;
for (int i = 0; i < n - 1; i++) {
int a = h[i][0];
int b = h[i][1];
int c = l[i];
g[a].push_back(make_pair(b, c));
g[b].push_back(make_pair(a, c));
}
centroid_decomposition();
return answ;
}
