#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
//const ll mod = 1e9+7;
bool maximize(ll &x, ll y ){
if (x < y) {x = y; return true;};
return false;
}
bool minimize(int &x, int y){
if (x > y) {x = y; return true;}
return false;
}
//void add(ll &x, ll y ){
// x += y;
// if (x >= mod) x -= mod;
//}
//void sub(ll &x, ll y) {
// x -= y;
// if (x < 0) x += mod;
//}
const int maxn = 2e5+5;
const int maxx = 1e9+7;
int n, k;
vector<pii> a[maxn];
bitset<maxn> del;
int child[maxn];
int sz, root;
int ans = maxx;
void couchild(int u, int p) {
child[u] = 1;
for (int i = 0; i <(int)a[u].size(); i++) {
int v = a[u][i].fi;
if (v == p || del[v]) continue;
couchild(v, u);
child[u] += child[v];
}
}
int centroid(int u, int p) {
for (int i = 0 ;i < (int)a[u].size(); i++) {
int v = a[u][i].fi;
if (v == p || del[v]) continue;
if (child[v] >= (sz >> 1)) return centroid(v, u);
}
return u;
}
int h[maxn];
int dis[maxn];
int tk[1000007];
vector<pii> temp;
void dfs(int u, int p) {
temp.push_back({dis[u], h[u]});
if (tk[k-dis[u]] < maxx) {
minimize(ans, h[u] + tk[k-dis[u]]);
}
for (int i = 0; i < (int)a[u].size(); i++) {
int v = a[u][i].fi;
if (v == p || del[v]) continue;
int w = a[u][i].se;
if (dis[u] + w > k) continue;
dis[v] = dis[u] + w;
h[v] = h[u] + 1;
dfs(v, u);
}
}
void dfsr(int u, int p) {
tk[dis[u]] = maxx;
for (int i = 0; i < (int)a[u].size(); i++) {
int v = a[u][i].fi;
if (v == p || del[v]) continue;
int w = a[u][i].se;
if (dis[u] + w > k) continue;
dfsr(v, u);
}
}
void solve(int u) {
couchild(u, 0);
sz = child[u];
//get centroid
root = centroid(u, 0);
//dfs solve
h[root] = dis[root] = 0;
for (int i = 0; i < (int)a[root].size(); i++) {
int v = a[u][i].first, w = a[u][i].se;
if (del[v]) continue;
if (w > k) continue;
dis[v] = dis[u] + w;
h[v] = h[u]+1;
dfs(v, u);
for (int i = 0; i < (int)temp.size(); i++) {
minimize(tk[temp[i].fi], temp[i].se);
}
temp.clear();
}
//dfs erase
dfsr(root, 0);
del[root] = true;
//solve sub
for (int i = 0; i < (int)a[root].size(); i++) {
int v = a[u][i].first;
if (del[v]) continue;
solve(v);
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for (int i = 1; i <= n; i++) {
int u = H[i][0], v = H[i][1];
int w = L[i];
a[u].pb({v, w});
a[v].pb({u, w});
}
for (int i = 1; i <= k; i++) {
tk[i] = maxx;
}
solve(1);
return ans;
}
