#include <bits/stdc++.h>
using namespace std;
const int N = 200200, oo = 1 << 21;
int n, k, h[N][2], l[N], height[N], pos[N], deltaVal[N], st[N], last, curChild[N], par[N];
long long deltaID[N];
vector<pair<int, int>> a[N];
vector<int> order;
map<long long, int> m[N];
int ans = oo;
int unionMap(int u, int v, int c)
{
int res = oo;
long long offsetID = c + deltaID[u] + deltaID[v];
int offsetVal = 1 + deltaVal[u] + deltaVal[v];
for (auto it : m[v])
if (m[u].count(k - it.first - offsetID))
res = min(res, it.second + m[u][k - it.first - offsetID] + offsetVal);
offsetID = c + deltaID[v] - deltaID[u];
offsetVal = 1 + deltaVal[v] - deltaVal[u];
for (auto it : m[v])
if (!m[u].count(it.first + offsetID) || m[u][it.first + offsetID] > it.second + offsetVal)
m[u][it.first + offsetID] = it.second + offsetVal;
m[v].clear();
return res;
}
int calc(int x)
{
int mxSize = 0, res = oo, tmp;
pos[x] = x;
for (auto u : a[x])
{
int y = u.first;
if (y == par[x]) continue;
int sizeY = m[pos[y]].size();
if (sizeY > mxSize)
{
mxSize = sizeY;
pos[x] = pos[y];
tmp = u.second;
}
}
if (pos[x] == x)
{
m[x][0] = 0;
return res;
}
int u = pos[x];
deltaID[u] += tmp;
deltaVal[u]++;
if (m[u].count(k - deltaID[u]))
res = min(res, m[u][k - deltaID[u]] + deltaVal[u]);
if (!m[u].count(-deltaID[u]) || m[u][-deltaID[u]] > -deltaVal[u])
m[u][-deltaID[u]] = -deltaVal[u];
for (auto u : a[x])
{
int y = u.first;
if (y == par[x] || pos[x] == pos[y]) continue;
res = min(res, unionMap(pos[x], pos[y], u.second));
}
return res;
}
void dfs(int x)
{
for (auto u : a[x])
{
int y = u.first;
if (y == par[x])
continue;
par[y] = x;
dfs(y);
}
ans = min(ans, calc(x));
}
int best_path(int _n, int _k, int h[][2], int l[])
{
n = _n;
k = _k;
for (int i = 0; i < n - 1; i++)
{
a[h[i][0]].push_back({h[i][1], l[i]});
a[h[i][1]].push_back({h[i][0], l[i]});
}
par[0] = -1;
dfs(0);
return ans == oo ? -1 : ans;
}
