#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
struct my_hash {
const uint64_t RANDOM = chrono::steady_clock::now().time_since_epoch().count();
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
return splitmix64(x + RANDOM);
}
};
const int mxN = 200000;
int n, k, ans, sz[mxN];
bool dead[mxN];
vector<pair<int, int>> adj[mxN];
int dfs_sz(int u, int p) {
sz[u] = 1;
for (pair<int, int> v : adj[u]) if (v.first != p && !dead[v.first])
sz[u] += dfs_sz(v.first, u);
return sz[u];
}
int get_centroid(int u, int p, int tree_sz) {
for (pair<int, int> v : adj[u]) if (v.first != p && !dead[v.first] && 2 * sz[v.first] > tree_sz)
return get_centroid(v.first, u, tree_sz);
return u;
}
gp_hash_table<int, int, my_hash> mp, mp2;
void upd(int wd, int d, gp_hash_table<int, int, my_hash>& m) {
auto it = m.find(wd);
if (it == m.end()) {
m[wd] = d;
}
else {
it->second = min(it->second, d);
}
}
void dfs(int u, int p, int d, int wd, gp_hash_table<int, int, my_hash>& m) {
if (wd > k) return;
if (wd == k) {
ans = min(ans, d);
return;
}
upd(wd, d, m);
for (pair<int, int> v : adj[u]) if (v.first != p && !dead[v.first]) {
dfs(v.first, u, d + 1, wd + v.second, m);
}
}
void centroid(int u = 0) {
u = get_centroid(u, -1, dfs_sz(u, -1));
dfs_sz(u, -1);
int big = -1;
for (pair<int, int> v : adj[u]) if (!dead[v.first]) {
if (big == -1 || sz[v.first] > sz[big]) {
big = v.first;
}
}
if (big == -1) return;
for (pair<int, int> v : adj[u]) if (v.first == big) {
dfs(v.first, u, 1, v.second, mp);
}
for (pair<int, int> v : adj[u]) if (!dead[v.first] && v.first != big) {
dfs(v.first, u, 1, v.second, mp2);
for (const pair<int, int>& p : mp2) {
auto it = mp.find(k - p.first);
if (it != mp.end()) {
ans = min(ans, p.second + it->second);
}
}
for (const pair<int, int>& p : mp2) {
upd(p.first, p.second, mp);
}
mp2.clear();
}
mp.clear();
dead[u] = 1;
for (pair<int, int> v : adj[u]) if (!dead[v.first]) {
centroid(v.first);
}
dead[u] = 0;
}
int best_path(int _n, int _k, int h[][2], int l[]) {
n = _n, k = _k, ans = INT_MAX;
for (int i = 0; i < n - 1; ++i) {
int u = h[i][0], v = h[i][1], w = l[i];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
centroid();
if (ans == INT_MAX) ans = -1;
return ans;
}
/*int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k; cin >> n >> k;
int h[n - 1][2];
int l[n - 1];
for (int i = 0; i < n - 1; ++i) {
cin >> h[i][0] >> h[i][1];
}
for (int i = 0; i < n - 1; ++i) {
cin >> l[i];
}
cout << best_path(n, k, h, l);
return 0;
}
*/
