#include <bits/stdc++.h>
using namespace std;
#ifndef KURUMI
#include "race.h"
#endif
#define endl '\n'
#define fi first
#define se second
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "[" #x " = " << (x) << "]"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> bool maximize(T &a, T b) {
if(a < b) {
a = b;
return true;
}else return false;
}
template<typename T> bool minimize(T &a, T b) {
if(a > b) {
a = b;
return true;
}else return false;
}
template<typename T> T rnd(T a, T b) {
return uniform_int_distribution<T>(a, b)(rng);
}
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, int> pli;
typedef pair<long long, long long> pll;
const int N = 2e5 + 3;
int n, k;
vector<pii> adj[N];
int answer = INT_MAX;
int siz[N];
bool isCentroid[N];
map<int, int> lens;
void dfsSize(int u, int p) {
siz[u] = 1;
for(pii it : adj[u]) {
int v, w; tie(v, w) = it;
if(v != p && !isCentroid[v]) {
dfsSize(v, u);
siz[u] += siz[v];
}
}
}
int findCentroid(int u, int p, int treeSize) {
for(pii it : adj[u]) {
int v = it.fi;
if(v != p && !isCentroid[v] && siz[v] > treeSize / 2) {
return findCentroid(v, u, treeSize);
}
}
return u;
}
void update(int u, int p, int wgt, int len) {
if(lens.count(k - wgt))
minimize(answer, len + lens[k - wgt]);
for(pii it : adj[u]) {
int v, w; tie(v, w) = it;
if(!isCentroid[v] && v != p) {
update(v, u, wgt + w, len + 1);
}
}
}
void add(int u, int p, int wgt, int len) {
if(wgt <= k) {
if(lens.count(wgt)) minimize(lens[wgt], len);
else lens[wgt] = len;
}
for(pii it : adj[u]) {
int v, w; tie(v, w) = it;
if(!isCentroid[v] && v != p) {
add(v, u, wgt + w, len + 1);
}
}
}
void decompose(int u) {
dfsSize(u, -1);
u = findCentroid(u, -1, siz[u]);
lens.clear(); lens[0] = 0;
for(pii it : adj[u]) {
int v, w; tie(v, w) = it;
if(!isCentroid[v]) {
update(v, u, w, 1);
add(v, u, w, 1);
}
}
isCentroid[u] = true;
for(pii it : adj[u]) {
int v = it.fi;
if(!isCentroid[v]) decompose(v);
}
}
int process() {
dfsSize(1, -1);
decompose(1);
return (answer == INT_MAX ? -1 : answer);
}
int best_path(int _n, int _k, int _h[][2], int _l[]) {
n = _n; k = _k;
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);
}
return process();
}
