#include "race.h"
#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x, y) make_pair(x, y)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)
#define ppb() pop_back()
#define tr(ii, c) for (__typeof((c).begin()) ii = (c).begin(); ii != (c).end(); ii++)
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
template <class T>
bool umin(T &a, T b)
{
if (a > b)
{
a = b;
return 1;
}
return 0;
}
template <class T>
bool umax(T &a, T b)
{
if (a < b)
{
a = b;
return 1;
}
return 0;
}
int n, k, ans = INF;
ll dis[MAXN];
vector<PII> adj[MAXN];
set<pair<ll, int>> s[MAXN];
void dfs(int nd, int pr, int lvl)
{
tr(it, adj[nd])
{
int to = it->ff;
if (to != pr)
{
dis[to] = dis[nd] + it->ss;
dfs(to, nd, lvl + 1);
if ((int)s[to].size() > (int)s[nd].size())
swap(s[to], s[nd]);
__typeof((s[nd]).begin()) itt;
tr(it, s[to]) if (dis[nd] * 2 + k >= it->ff)
{
itt = s[nd].lower_bound(mp(dis[nd] * 2 + k - it->ff, -1));
if (itt != s[nd].end() and itt->ff + it->ff == k + dis[nd] * 2)
umin(ans, it->ss + itt->ss - 2 * lvl);
}
tr(it, s[to]) s[nd].insert(*it);
s[to].clear();
}
}
s[nd].insert(mp(dis[nd], lvl));
__typeof((s[nd]).begin()) itt = s[nd].lower_bound(mp(k + dis[nd], -1));
if (itt != s[nd].end() and itt->ff - dis[nd] == k)
umin(ans, itt->ss - lvl);
}
int best_path(int N, int K, int h[][2], int l[])
{
n = N, k = K;
for (int i = 0; i < n - 1; i++)
{
int u = h[i][0], v = h[i][1];
adj[u].pb(mp(v, l[i]));
adj[v].pb(mp(u, l[i]));
}
dfs(1, -1, 0);
if (ans == INF)
ans = -1;
return ans;
}
