/**
* \author Nguyen Duc Kien
* \date ./08/2021
*/
///Task name
#define TASK ""
///-------------------------------------------///
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const int maxnn = 1e6 + 5;
int n, k, res;
vector <pair <int, int> > G[maxn];
namespace BF
{
void DFS(int u, int d, int l, int par = 0)
{
if (l > k) return;
if (l == k) res = min(res, d);
for (auto p : G[u])
{
int v = p.first;
int w = p.second;
if (v == par) continue;
DFS(v, d + 1, l + w, u);
}
}
void Main()
{
for (int i = 1; i <= n; i ++) DFS(i, 0, 0);
}
}
namespace Centroid
{
int sz[maxn], mpath[maxnn];
bool mk[maxn];
void DFS_sz(int u, int par = 0)
{
sz[u] = 1;
for (auto p : G[u])
{
int v = p.first;
if (v == par || mk[v]) continue;
DFS_sz(v, u);
sz[u] += sz[v];
}
}
void DFS_mpath(int u, int d, long long l, int par, int com)
{
if (l > k) return;
if (com == 0)
{
res = min(res, d + mpath[k - l]);
}
else if (com == 1)
{
mpath[l] = min(mpath[l], d);
}
else if (com == -1)
{
mpath[l] = 1e9 + 69;
}
for (auto p : G[u])
{
int v = p.first;
int w = p.second;
if (v == par || mk[v]) continue;
DFS_mpath(v, d + 1, l + w, u, com);
}
}
int GetCentroid(int u, int msz, int par = 0)
{
for (auto p : G[u])
{
int v = p.first;
if (v == par || mk[v]) continue;
if (sz[v] * 2 > sz[u]) return GetCentroid(v, msz, u);
}
return u;
}
void Centroid(int u)
{
DFS_sz(u);
int cent = GetCentroid(u, sz[u]);
mk[cent] = 1;
for (auto p : G[cent])
{
int v = p.first;
int w = p.second;
if (mk[v]) continue;
DFS_mpath(v, 1, w, cent, 0);
DFS_mpath(v, 1, w, cent, 1);
}
if (mpath[k]) res = min(res, mpath[k]);
for (auto p : G[cent])
{
int v = p.first;
int w = p.first;
if (mk[v]) continue;
DFS_mpath(v, 1, w, cent, -1);
}
for (auto p : G[cent])
{
int v = p.first;
if (mk[v]) continue;
Centroid(v);
}
}
void Init()
{
fill(mpath + 1, mpath + 1000001, 1e9 + 69);
res = 1e9 + 69;
}
}
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] + 1;
int v = __h[i][1] + 1;
int w = __l[i];
G[u].push_back({v, w});
G[v].push_back({u, w});
}
Centroid::Init();
// Centroid::Centroid(1);
BF::Main();
return (res == 1e9 + 69 ? -1 : res);
}
