#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
using namespace std;
const int Ni = 200001;
const int Ki = 1e6+1;
vector<pair<int,int>> adj[Ni];
vector<int> cnt;
bool cen[Ni];
int sz[Ni];
int mini = Ni;
int k;
void dsz(int u, int p) {
sz[u] = 1;
for(pair<int,int> i : adj[u]) {
if (i.first != p && !cen[i.first]) {
dsz(i.first,u);
sz[u] += sz[i.first];
}
}
}
int centroid(int u,int p,int n) {
for(pair<int,int> i : adj[u]) {
if (i.first != p && 2*sz[i.first] > n && !cen[i.first]) return centroid(i.first,u,n);
}
return u;
}
void find(int u, int p, int currl, int ps, bool add) {
if (ps > k) return;
if (add) cnt[ps] = cnt[ps]==-1 ? currl : min(cnt[ps],currl);
else if (cnt[k-ps] != -1) mini = min(mini,currl+cnt[k-ps]);
for(pair<int,int> i : adj[u]) {
if (i.first != p && !cen[i.first]) {
find(i.first,u,currl+1,ps+i.second,add);
}
}
}
void del(int u, int p, int ps) {
if (ps > k) return;
cnt[ps] = -1;
for(pair<int,int> i : adj[u]){
if (i.first != p && !cen[i.first]) del(i.first,u,ps+i.second);
}
}
void solve(int u, int centr) {
dsz(u,centr);
int cent = centroid(u,centr,sz[u]);
cen[cent]=true;
for(pair<int,int> i : adj[cent]) {
if (!cen[i.first]) {
find(i.first,cent,1,i.second,0);
find(i.first,cent,1,i.second,1);
}
}
for(pair<int,int> i : adj[cent]) {
if (!cen[i.first]) {
del(i.first,cent,i.second);
}
}
for(pair<int,int> i : adj[cent]) {
if (!cen[i.first]) solve(i.first,cent);
}
}
int best_path(int N,int K,int H[][2],int L[]) {
for(int i = 0; i < N; i++) {
adj[H[i][0]].push_back({H[i][1],L[i]});
adj[H[i][1]].push_back({H[i][0],L[i]});
}
k=K;
cnt.resize(K+1);
fill(begin(cnt),end(cnt),-1);
cnt[0] = 0;
solve(1,-1);
return mini == Ni ? -1 : mini;
}
