#include <bits/stdc++.h>
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
#define sz(x) (int)x.size()
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;
const int INF = 1e9 + 1;
const int MX = 2e5 + 100;
const double eps = 1e-7;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template<class T, size_t SZ> using AR = array<T, SZ>;
template<class T> using PR = pair<T, T>;
template <typename XPAX>
bool ckma(XPAX &x, XPAX y) {
return (x < y ? x = y, 1 : 0);
}
template <typename XPAX>
bool ckmi(XPAX &x, XPAX y) {
return (x > y ? x = y, 1 : 0);
}
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
V<ll> dis(MX);
V<int> ms(MX);
VV<pair<int, ll>> g(MX);
V<int> dep(MX);
int n;
ll k;
V<int> tin(MX), tout(MX);
int T = 1;
int ret = INF;
multiset<int> Bs[MX];
V<int> val(MX);
V<int> mp(MX);
map<ll, int> UD;
int get_id(ll x) {
if(UD[x])
return UD[x];
else return -1;
}
void dfs1(int v, int p) {
tin[v] = T++;
mp[T - 1] = v;
dep[v] = (p == 0 ? 0 : dep[p] + 1);
for(auto [c, w] : g[v]) {
if(c != p) {
dis[c] =dis[v] + w;
dfs1(c, v);
}
}
tout[v] = T;
ms[v] = tout[v] - tin[v];
}
void dfs2(int v, int p, bool keep) {
int mx = -1, bg = -1;
for(auto [c, w] : g[v])
if(c != p && ms[c] > mx)
mx = ms[c], bg = c;
for(auto [c, w] : g[v])
if(c != p && c != bg)
dfs2(c, v, 0);
if(bg != -1)
dfs2(bg, v, 1);
Bs[val[v]].insert(dep[v]);
int prx = dis[v] + k;
prx = get_id(prx);
if(prx != -1 && sz(Bs[prx]))
ckmi(ret, *Bs[prx].begin() - dep[v]);
for(auto [c, w] : g[v]) {
if(c != p && c != bg) {
//debug(v, c);
for(int x = tin[c];x < tout[c];++x) {
if(dis[v] + k == dis[mp[x]]) {
ckmi(ret, dep[mp[x]] - dep[v]);
}
else if(dis[mp[x]] - dis[v] < k) {
ll rr = dis[mp[x]] - dis[v];
rr = k - rr;
rr += dis[v];
assert(dis[v] + k > rr);
int id = get_id(rr);
if(id != -1 && sz(Bs[id]))
ckmi(ret, *Bs[id].begin() + dep[mp[x]] - 2 * dep[v]);
}
}
for(int x= tin[c];x < tout[c];++x)
Bs[val[mp[x]]].insert(dep[mp[x]]);
}
}
if(keep == 0)
for(int x = tin[v];x < tout[v];++x)
Bs[val[mp[x]]].erase(Bs[val[mp[x]]].find(dep[mp[x]]));
}
int best_path(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
forn(i, N) {
++H[i][0], ++H[i][1];
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
dfs1(1, 0);
int cor = 1;
for(int i = 1;i <= n;++i)
val[i] = (UD[dis[i]] ? UD[dis[i]] : UD[dis[i]] = cor++);
dfs2(1, 0, 1);
if(ret == INF)
ret = -1;
return ret;
}
