#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "IOI11_race"
//void Fi(){
// if(fopen(PROB".inp", "r")){
// freopen(PROB".inp", "r", stdin);
// freopen(PROB".out", "w", stdout);
// }
//}
const int INF = 1e9;
using pi = pair<int, int>;
vector<bool> vis;
vector<int> sz, mned, mark;
vector<vector<pi>> adj;
int lengthPath, ti, ans;
int dfs(int u, int p){
sz[u] = 1;
for(auto [w, v]: adj[u]) if(v != p && !vis[v]){
sz[u] += dfs(v, u);
}
return sz[u];
}
int centroid(int u, int p, int n){
for(auto [w, v]: adj[u]) if(v != p && !vis[v]){
if(sz[v] > n / 2) return centroid(v, u, n);
}
return u;
}
stack<pi> tmp;
void dfs2(int u, int p, int dis, int edg){
if(dis > lengthPath) return;
if(mark[lengthPath - dis] == ti){
ans = min(ans, edg + mned[lengthPath - dis]);
}
tmp.emplace(dis, edg);
for(auto [w, v]: adj[u]) if(v != p && !vis[v]){
dfs2(v, u, dis + w, edg + 1);
}
}
void build(int u, int p){
int c = centroid(u, p, dfs(u, p));
mned[0] = 0;
mark[0] = ++ti;
for(auto [w, v]: adj[c]) if(!vis[v]){
dfs2(v, c, w, 1);
for(; !tmp.empty(); tmp.pop()){
auto [dis, edg] = tmp.top();
if(mark[dis] == ti){
mned[dis] = min(mned[dis], edg);
} else{
mned[dis] = edg;
mark[dis] = ti;
}
}
}
vis[c] = true;
for(auto [w, v]: adj[c]) if(!vis[v]){
build(v, c);
}
}
int best_path(int n, int k, int h[][2], int l[]){
sz.resize(n);
adj.clear(); adj.resize(n);
vis.assign(n, false);
mned.resize(k + 1);
mark.assign(k + 1, 0);
ti = 0;
lengthPath = k;
ans = INF;
FOR(i, 0, n - 1){
adj[h[i][0]].eb(l[i], h[i][1]);
adj[h[i][1]].eb(l[i], h[i][0]);
}
build(0, -1);
return (ans == INF ? -1 : ans);
}
//const int N = 2e5 + 1;
//int n, k;
//int h[N][2], l[N];
//
//void enter(){
// cin >> n >> k;
// FOR(i, 0, n - 1) cin >> h[i][0] >> h[i][1];
// FOR(i, 0, n - 1) cin >> l[i];
//}
//
//int main(){
// IOS;
// Fi();
// enter();
// cout << best_path(n, k, h, l);
// return 0;
//}
