#include <bits/stdc++.h>
#include "race.h"
typedef long long ll;
#define F first
#define S second
using namespace std;
using pii = pair<int,int>;
const int N = 2e5 + 5, M = 1e6 + 5, inf = 1e8;
int k, mn[M], ans = inf, sz[N];
set<int> s;
vector<pii> g[N];
bool ded[N];
void dfs(int u, int p, int d, ll w){
if(w == k) ans = min(ans, d);
if(w < k) ans = min(ans, d + mn[k - w]);
for(pii it : g[u]) if(it.S != p && !ded[it.S]) dfs(it.S, u, d + 1, w + it.F);
}
void efs(int u, int p, int d, ll w){
if(w <= k) mn[w] = min(mn[w], d), s.insert(w);
for(pii it : g[u]) if(it.S != p && !ded[it.S]) efs(it.S, u, d + 1, w + it.F);
}
int fsz(int u, int p){
sz[u] = 1;
for(pii it: g[u]) if(it.S != p && !ded[it.S]) sz[u] += fsz(it.S, u);
return sz[u];
}
int fcen(int u, int p, int tsz){
for(pii it: g[u]) if(it.S != p && !ded[it.S] && sz[it.S] > tsz/2) return fcen(it.S, u, tsz); return u;
}
void cd(int u){
ded[u = fcen(u, -1, fsz(u, -1))] = true; s.clear();
for(pii it : g[u]) if(!ded[it.S]) dfs(it.S, u, 1, it.F), efs(it.S, u, 1, it.F);
for(int w : s) mn[w] = inf;
for(pii it: g[u]) if(!ded[it.S]) cd(it.S);
}
int best_path(int n, int K, int e[][2], int l[]){
for(int i = 0; i<n; ++i) g[i].clear();
k = K;
for(int i = 0; i<n-1; ++i){
int u = e[i][0], v = e[i][1], w = l[i];
g[u].emplace_back(w, v); g[v].emplace_back(w, u);
}
fill(sz, sz+n, 0); fill(ded, ded+n, false); fill(mn, mn+k+1, ans = inf);
cd(0);
return (ans >= inf)? -1 : ans;
}
/*
signed main(){
int n, K; scanf("%d %d", &n, &K);
int e[n][2], l[n];
for(int i = 0, u, v; i<n-1; ++i) scanf("%d %d", &e[i][0], &e[i][1]);
for(int i = 0; i<n-1; ++i) scanf("%d", l+i);
printf("%d\n", best_path(n, K, e, l));
}
*/
