#include <bits/stdc++.h>
using namespace std;
void fastIO(){
ios_base::sync_with_stdio(false);
cin.tie(0);
}
typedef long long ll;
vector<pair<int, int> > edges[200100];
int sub[200100];
bool rem[200100];
int LEN;
void dfs(int node, int pa = 0){
sub[node] = 1;
for (pair<int, int> nx : edges[node]){
if (nx.first == pa || rem[nx.first])
continue;
dfs(nx.first, node);
sub[node] += sub[nx.first];
}
}
int centroid(int node, int sz, int pa = 0){
for (pair<int, int> nx : edges[node]){
if (nx.first == pa || rem[nx.first])
continue;
if (sub[nx.first] > sz/2)
return centroid(nx.first, sz, node);
}
return node;
}
void dfs2(int node, ll dep, int cur, map<ll, int> &mp, int pa = 0){
if (mp.count(dep))
mp[dep] = min(mp[dep], cur);
else
mp[dep] = cur;
for (pair<int, int> nx : edges[node]){
if (nx.first == pa || rem[nx.first])
continue;
dfs2(nx.first, dep+nx.second, cur+1, mp, node);
}
}
int INF = 0x3f3f3f3f;
int decomp(int node){
dfs(node);
int cent = centroid(node, sub[node]);
rem[cent] = true;
map<ll, int> mp;
int curmin = INF;
mp[0] = 0;
for (pair<int, int> nx : edges[cent]){
if (rem[nx.first])
continue;
map<ll, int> tmp;
dfs2(nx.first, nx.second, 1, tmp);
for (auto it = tmp.begin(); it != tmp.end(); it++){
if (mp.count(LEN-(*it).first))
curmin = min(curmin, (*it).second+mp[LEN-(*it).first]);
}
for (auto it = tmp.begin(); it != tmp.end(); it++){
if (!mp.count((*it).first))
mp[(*it).first] = (*it).second;
else
mp[(*it).first] = min(mp[(*it).first], (*it).second);
}
}
int totmin = curmin;
for (pair<int, int> nx : edges[cent]){
if (rem[nx.first])
continue;
int val = decomp(nx.first);
if (val == -1)
continue;
totmin = min(totmin, val);
}
if (totmin == INF)
return -1;
return totmin;
}
int best_path(int N, int K, int H[][2], int *L){
LEN = K;
for (int i = 0; i < N-1; i++){
int a = H[i][0], b = H[i][1];
a++, b++;
edges[a].push_back({b, L[i]});
edges[b].push_back({a, L[i]});
}
return decomp(1);
}
