#include <bits/stdc++.h>
#define ll long long
#define int ll
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define pi pair<int,int>
#define pii pair<int,pi>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(a) (int) a.size()
#define endl '\n'
#define data "data"
using namespace std;
const ll linf = 1e18;
const int inf = 1e9;
const int MOD = 1e9 + 7, M = 3e5;
const int MX = 1e6;
void add(int &a, int b)
{
a += b;
if(a>=MOD)
a-=MOD;
if(a<0)
a += MOD;
}
int modulo(int x)
{
if(x<=1)
return 1;
return (MOD - MOD/x) * modulo(MOD/x) % MOD;
}
int mul(int a, int b)
{
return (1ll *a%MOD * b%MOD) % MOD;
}
int ans = inf;
int n, k;
int mn[MX+3];
int Sz[M];
bool iscent[M];
vector<pi> adj[M];
void dfs(int u, int p)
{
Sz[u] = 1;
FOR(i, 0, sz(adj[u]) -1)
{
int v = adj[u][i].fi;
if(v == p || iscent[v]) continue;
dfs(v, u);
Sz[u] += Sz[v];
}
}
int find_cent(int u, int tree_sz, int p)
{
FOR(i, 0, sz(adj[u]) -1)
{
int v = adj[u][i].fi;
if(v == p || iscent[v] || Sz[v] * 2 < tree_sz) continue;
return find_cent(v, tree_sz, u);
}
return u;
}
void compute(int u, int dept, bool f, int sum, int p)
{
if(sum > k) return;
if(f == 1)
{
if(k >= sum)
ans = min(ans, mn[k - sum] + dept);
}
else
{
mn[sum] = min(mn[sum], dept);
}
FOR(i, 0, sz(adj[u]) -1)
{
int v = adj[u][i].fi, w = adj[u][i].se;
if(iscent[v] || v == p) continue;
compute(v, dept + 1, f, sum + w, u);
}
}
void Erase(int u, int dept, int sum, int p)
{
if(sum > k) return;
mn[sum] = inf;
FOR(i, 0, sz(adj[u]) -1)
{
int v = adj[u][i].fi, w = adj[u][i].se;
if(iscent[v] || v == p) continue;
Erase(v, dept + 1, sum + w, u);
}
}
void build_cent(int u)
{
dfs(u, -1);
int cur = find_cent(u, Sz[u], u);
iscent[cur] = 1;
mn[0] = 0;
FOR(i, 0, sz(adj[cur]) -1)
{
int v = adj[cur][i].fi, w = adj[cur][i].se;
if(iscent[v]) continue;
compute(v, 1, 1, w, cur);
compute(v, 1, 0, w, cur);
}
FOR(i, 0, sz(adj[cur]) -1)
{
int v = adj[cur][i].fi, w = adj[cur][i].se;
if(iscent[v]) continue;
Erase(v, 1, w, u);
}
FOR(i, 0, sz(adj[cur]) -1)
{
int v = adj[cur][i].fi;
if(iscent[v]) continue;
build_cent(v);
}
}
void solve(void)
{
FOR(i, 0, M) mn[i] = inf;
build_cent(1);
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N;
k = K;
FOR(i, 0, n - 2)
{
int u = H[i][0] + 1;
int v = H[i][1] + 1;
adj[u].pb({v, L[i]});
adj[v].pb({u, L[i]});
}
solve();
return ans;
}
