#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define el "\n"
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
const ll N = 1e6 + 7;
const ll mod = 1e9 + 7;
int dx[] = {0, -1, 0, 1, -1, 1, -1, 1};
int dy[] = {-1, 0, 1, 0, 1, -1, -1, 1};
ll n, m, k, y, x, l, r;
vector<pair<int, ll>> adj[N];
int sz[N], dad[N];
bool vis[N];
map<ll, int> mn;
map<ll, int> cnt;
int ans = 1e9;
int dfs_sz(int node, int par) {
sz[node] = 1;
for (auto j: adj[node]) {
if (j.first == par || vis[j.first]) {
continue;
}
sz[node] += dfs_sz(j.first, node);
}
return sz[node];
}
int dfs_cen(int node, int par, int ch) {
for (auto j: adj[node]) {
if (sz[j.first] > ch / 2 && !vis[j.first] && j.first != par) {
return dfs_cen(j.first, node, ch);
}
}
return node;
}
vector<pair<ll, int>> pool;
void dfs_coll(int node, int par, ll dis, int cur) {
pool.push_back({dis, cur});
for (auto j: adj[node]) {
if (vis[j.first] || j.first == par) {
continue;
}
dfs_coll(j.first, node, dis + j.second, cur + 1);
}
}
void build(int node, int par) {
int sz = dfs_sz(node, par);
int cen = dfs_cen(node, par, sz);
if (par == -1) {
par = cen;
}
vis[cen] = 1;
cnt[0] = 1;
for (auto j: adj[cen]) {
if (vis[j.first]) {
continue;
}
pool.clear();
dfs_coll(j.first, cen, j.second, 1);
for (auto l: pool) {
if (l.first <= k) {
if (mn[k - l.first] || l.first == k) {
ans = min(ans, l.second + mn[k - l.first]);
}
}
}
for (auto l: pool) {
if (!mn[l.first]) {
mn[l.first] = l.second;
}
mn[l.first] = min(mn[l.first], l.second);
}
}
mn.clear();
for (auto j: adj[cen]) {
if (vis[j.first]) {
continue;
}
build(j.first, cen);
}
return;
}
int best_path(int N,int K,int H[][2],int L[])
{
k=K;
n=N;
for (int i=0;i<n-1;i++)
{
adj[H[i][0]].push_back({H[i][1],L[i]});
adj[H[i][1]].push_back({H[i][0],L[i]});
}
build(0,-1);
if (ans==1e9)
{
ans=-1;
}
return ans;
}
//void dowork() {
// cin >> n >> k;
// int w;
// for (int i = 1; i < n; i++) {
// cin >> x >> y >> w;
// adj[x].push_back({y, w});
// adj[y].push_back({x, w});
// }
// build(0, -1);
// if (ans == 1e9) {
// ans = -1;
// }
// cout << ans << el;
//}
//
//int main() {
// fast
// //freopen("barnparinting.in","r",stdin);
// //freopen("barnparinting.out","w",stdout);
// int t = 1;
// //cin >> t;
// for (int i = 1; i <= t; i++) {
// dowork();
// }
//}
