#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
vector<vector<pair<int, ll>>> G;
int K;
vector<bool> C_vis;
vector<int> subtr;
int dfs_subtr(int v, int p) {
subtr[v] = 1;
for(auto [sas, w] : G[v])
if(sas != p && !C_vis[sas])
subtr[v] += dfs_subtr(sas, v);
return subtr[v];
}
int find_cen(int v, int p, int s) {
for(auto [sas, w] : G[v])
if(sas != p && !C_vis[sas] && subtr[sas] > s/2) return find_cen(sas, v, s);
return v;
}
int wyn = INT_MAX;
void dfs(int v, int p, unordered_map<ll, int>& m, ll D, int d) {
if(m.find(D) == m.end()) m[D] = d;
else m[D] = min(m[D], d);
for(auto [sas, w] : G[v])
if(sas != p && !C_vis[sas])
dfs(sas, v, m, D+w, d+1);
}
void count(int c) {
int s = dfs_subtr(c, c);
c = find_cen(c, c, s);
C_vis[c] = true;
for(auto [sas, w] : G[c])
if(!C_vis[sas]) count(sas);
unordered_map<ll, int> m;
m[0] = 0;
for(auto [sas, w] : G[c]) {
unordered_map<ll, int> m2;
dfs(sas, c, m2, w, 1);
for(auto [D, d] : m2)
if(m.find(K-D) != m.end()) wyn = min(wyn, m[K-D] + d);
for(auto [D, d] : m2)
if(m.find(D) == m.end()) m[D] = d;
else m[D] = min(m[D], d);
}
}
int best_path(int n, int K, int H[][2], int L[])
{
G.clear(); G.resize(n);
for(int i = 0; i < n-1; i++) G[H[i][0]].push_back({H[i][1], L[i]}), G[H[i][1]].push_back({H[i][0], L[i]});
::K = K;
C_vis.clear(); C_vis.resize(n);
subtr.clear(); subtr.resize(n);
wyn = INT_MAX;
count(0);
return wyn == INT_MAX ? -1 : wyn;
}
//----------------
/*int main() {
int n, k; cin >> n >> k;
int H[n-1][2]; for(int i = 0; i < n-1; i++) cin >> H[i][0] >> H[i][1];
int L[n-1]; for(int i = 0; i < n-1; i++) cin >> L[i];
cout << best_path(n, k, H, L) << '\n';
}*/
