//khodaya khodet komak kon
# include "race.h"
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <pii, int> ppi;
typedef pair <int, pii> pip;
typedef pair <pii, pii> ppp;
typedef pair <ll, ll> pll;
# define A first
# define B second
# define endl '\n'
# define sep ' '
# define all(x) x.begin(), x.end()
# define kill(x) return cout << x << endl, 0
# define SZ(x) int(x.size())
# define lc id << 1
# define rc id << 1 | 1
# define fast_io ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}
const int xn = 2e5 + 10;
const int xm = 1e6 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 1e9 + 7;//998244353;
const int base = 257;
int sz[xn], ans = inf, a[xm], ptr, k;
pii b[xn];
bool hide[xn];
vector <pii> adj[xn];
void plant(int v, int p = - 1){
sz[v] = 1;
for (pii u : adj[v])
if (u.A != p && !hide[u.A])
plant(u.A, v), sz[v] += sz[u.A];
}
int find_centroid(int v, int s, int p = - 1){
for (pii u : adj[v])
if (u.A != p && !hide[u.A] && s < 2 * sz[u.A])
return find_centroid(u.A, s, v);
return v;
}
void DFS(int v, int p = - 1, int h = 0, int dis = 0){
if (k < dis)
return;
if (k == dis)
ans = min(ans, h);
else if (a[k - dis])
ans = min(ans, h + a[k - dis]);
b[ptr ++] = {dis, h};
for (pii u : adj[v])
if (u.A != p && !hide[u.A])
DFS(u.A, v, h + 1, dis + u.B);
}
void solve(int v){
plant(v);
v = find_centroid(v, sz[v]);
hide[v] = true;
vector <int> V;
for (pii u : adj[v]){
if (hide[u.A])
continue;
ptr = 0;
DFS(u.A, v, 1, u.B);
for (int i = 0; i < ptr; ++ i){
if (!a[b[i].A])
a[b[i].A] = inf;
a[b[i].A] = min(a[b[i].A], b[i].B);
V.push_back(b[i].A);
}
}
for (int x : V)
a[x] = 0;
for (pii u : adj[v])
if (!hide[u.A])
solve(u.A);
}
int best_path(int N, int K, int H[][2], int L[]){
k = K;
for (int i = 0; i < N - 1; ++ i){
int v = H[i][0], u = H[i][1], w = L[i];
adj[v].push_back({u, w});
adj[u].push_back({v, w});
}
solve(0);
if (ans == inf)
ans = - 1;
return ans;
}
/*
int main(){
fast_io;
count_routes();
return 0;
}
*/
/*
5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
*/
