#include "race.h"
#include <bits/stdc++.h>
///#include "grader.cpp"
using namespace std;
const int N_max = 2e5 + 2;
const int K_max = 1e6 + 2;
const int INF = 1e9 + 7;
vector < pair <int, int> > g[N_max];
bool vis[N_max];
int sz[N_max], k;
int ans;
int br[K_max];
void dfs1(int u, int p)
{
sz[u] = 1;
for (auto [v, w] : g[u])
{
if (v == p || vis[v])
{
continue;
}
dfs1(v, u);
sz[u] += sz[v];
}
}
int centroid(int u, int p, int n)
{
for (auto [v, w] : g[u])
{
if (v == p || vis[v])
{
continue;
}
if (sz[v] * 2 > n)
{
return centroid(v, u, n);
}
}
return u;
}
void dfs2(int u, int p, int len, int d)
{
if (len > k)
{
return;
}
ans = min(ans, d + br[k - len]);
for (auto [v, w] : g[u])
{
if (v == p || vis[v])
{
continue;
}
dfs2(v, u, len + w, d + 1);
}
}
void dfs3(int u, int p, int len, int d, vector <int> &tmp)
{
if (len > k)
{
return;
}
tmp.push_back(len);
br[len] = min(br[len], d);
for (auto [v, w] : g[u])
{
if (v == p || vis[v])
{
continue;
}
dfs3(v, u, len + w, d + 1, tmp);
}
}
void solve(int u)
{
dfs1(u, -1);
vector <int> tmp;
for (auto [v, w] : g[u])
{
if (vis[v])
{
continue;
}
dfs2(v, u, w, 1);
dfs3(v, u, w, 1, tmp);
}
vis[u] = 1;
for (auto c : tmp)
{
br[c] = INF;
}
for (auto [v, w] : g[u])
{
if (vis[v])
{
continue;
}
solve(centroid(v, u, sz[v]));
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
ans = INF;
for (int i = 0; i < N - 1; i++)
{
int u = H[i][0], v = H[i][1], w = L[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
for (int i = 1; i <= k; i++)
{
br[i] = INF;
}
dfs1(0, -1);
solve(centroid(0, -1, sz[0]));
if (ans == INF)
{
return -1;
}
return ans;
}
