#include <iostream>
#include <algorithm>
#include <vector>
#include <chrono>
#include <cmath>
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef int_fast8_t int8;
typedef int_fast16_t int16;
typedef int_fast32_t int32;
typedef int_fast64_t int64;
typedef int_fast64_t ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define PB push_back
#define PF push_front
#define MP make_pair
#define FF first
#define SS second
namespace hash0 {
const double PI = acos(-1);
struct chash {
const uint64_t C = ll(2e18*PI)+71;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
inline ll operator()(ll x) const { return __builtin_bswap64((x ^ RANDOM) * C); }
inline ll operator()(pii p) const { return __builtin_bswap64((p.FF ^ RANDOM) * C) + p.SS; }
};
template<class K, class V>
using fast_map = gp_hash_table<K, V, chash>;
template<class K>
using fast_set = fast_map<K, null_type>;
}
using namespace hash0;
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
return os << '(' << p.FF << ", " << p.SS << ')';
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const fast_map<T1, T2>& s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = ++s.begin(); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
int N, K;
vector<pii> adj[200005];
int W[200005];
bool R[200005];
int dfs_w(int u, int p) {
W[u] = 1;
for (pii v : adj[u])
if (v.FF != p && !R[v.FF])
W[u] += dfs_w(v.FF, u);
return W[u];
}
int centroid(int u, int n, int p) {
for (pii v : adj[u])
if (v.FF != p && !R[v.FF])
if (W[v.FF] * 2 > n)
return centroid(v.FF, n, u);
return u;
}
int ans = 2000000011;
vector<pii> V;
void dfs_u(int u, int p, int d, int t) {
if (d > K || t > ans)
return;
V.PB(MP(d, t));
for (pii v : adj[u])
if (v.FF != p && !R[v.FF])
dfs_u(v.FF, u, d + v.SS, t + 1);
}
void init_cd(int u) {
u = centroid(u, dfs_w(u, -1), -1);
fast_map<int, int> M;
for (pii v : adj[u]) {
if (R[v.FF])
continue;
dfs_u(v.FF, u, v.SS, 1);
for (pii x : V) {
if (M.find(K - x.FF) != M.end())
ans = min(ans, M[K - x.FF] + x.SS);
else if (x.FF == K)
ans = min(ans, x.SS);
}
for (pii x : V) {
if (M.find(x.FF) == M.end())
M[x.FF] = x.SS;
else
M[x.FF] = min(M[x.FF], x.SS);
}
V.clear();
}
R[u] = 1;
for (pii v : adj[u])
if (!R[v.FF])
init_cd(v.FF);
}
int best_path(int n, int k, int h[][2], int l[]) {
N = n, K = k;
for (int i = 0; i < n - 1; i++) {
adj[h[i][0]].PB(MP(h[i][1], l[i]));
adj[h[i][1]].PB(MP(h[i][0], l[i]));
}
init_cd(0);
return ans == 2000000011 ? -1 : ans;
}
