#include <bits/stdc++.h>
using namespace std;
// #define LOCAL
#ifdef LOCAL
#include "debug2.h"
#else
#define debug(...) 42
#endif
template<typename T> bool ckmin(T& x, const T& y) { return x > y ? x = y, 1 : 0; }
template<typename T> bool ckmax(T& x, const T& y) { return x < y ? x = y, 1 : 0; }
#define REP(i, n) for(int i = 0, ____n = (n); i < ____n; ++i)
#define REPD(i, n) for(int i = (n) - 1; i >= 0; --i)
#define left _______left
#define right _______right
#define MASK(x) (1LL << (x))
#define BIT(mask, x) (((mask) >> (x)) & 1)
#define SZ(x) (int) ((x).size())
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SQR(x) (1LL * (x) * (x))
#define BETWEEN(l, x, r) ((l) <= (x) && (x) <= (r))
#define pb push_back
const long long INF = (long long) 1e18 + 7;
const int MOD = (int) 1e9 + 7;
const int MX = (int) 2e5 + 5;
const int LG = __lg(MX) + 1;
const int BLOCK = 320;
const int MAX_K = (int) 1e6 + 5;
int N, K;
vector<pair<int, int>> adj[MX];
int sz[MX];
bool del[MX];
void countChild(int u, int p) {
sz[u] = 1;
for (auto [v, l] : adj[u]) if (v != p && !del[v]) {
countChild(v, u);
sz[u] += sz[v];
}
}
int centroid(int u, int p, int n) {
for (auto [v, l] : adj[u]) if (v != p && !del[v] && sz[v] > n / 2) return centroid(v, u, n);
return u;
}
vector<pair<int, int>> vec;
int timer = 0;
int exist[MAX_K];
long long ans;
long long min_dep[MAX_K];
void dfs(int u, int p, int dep, int len) {
if (len > K) return;
vec.pb(make_pair(dep, len));
if (exist[k - len] == timer) ckmin(ans, min_dep[K - len] + dep);
for (auto [v, l] : adj[u]) if (v != p && !del[v]) {
dfs(v, u, dep + 1, len + l);
}
}
void getAns(int root, int n) {
++timer;
exist[0] = timer;
for (auto [v, l] : adj[root]) if (!del[v]) {
vec.clear(); // (dep, len)
dfs(v, root, 1, l);
for (auto [dep, len] : vec) {
if (exist[len] != timer || (exist[len] == timer && min_dep[len] > dep)) {
exist[len] = timer;
min_dep[len] = dep;
}
}
}
}
void solve(int u) {
countChild(u, -1);
int n = sz[u];
int root = centroid(u, -1, n);
getAns(root, n);
del[root] = true;
for (auto [v, l] : adj[root]) if (!del[v]) solve(v);
}
int best_path(int n, int k, int edges[][2], int weights[]) {
N = n; K = k;
for (int i = 1; i < N; ++i) {
int u = edges[i][0] + 1, v = edges[i][1] + 1;
int l = weights[i];
adj[u].pb(make_pair(v, l));
adj[v].pb(make_pair(u, l));
}
memset(del, false, sizeof del);
memset(exist, -1, sizeof exist);
memset(min_dep, 0x3f, sizeof min_dep);
min_dep[0] = 0;
vec.clear();
ans = INF;
solve(1);
return ans == INF ? -1 : ans;
}
/**
**/
