#include <bits/stdc++.h>
#include "race.h"
#define FAST {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define FILES {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);}
#define ll long long
#define ull unsigned long long
#define pqueue priority_queue
#define pb push_back
#define fi first
#define se second
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) (a).begin(), (a).end()
#define mp make_pair
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key -> # less than k
// find_by_order -> k-th element
// pq max element
const double eps = 0.00000001;
const int NMAX = 2000010;
const ll inf = LLONG_MAX/3;
const ll modi = 998244353;
int K;
int visited[NMAX];
vector<pii>al[NMAX];
ll res = INT_MAX;
map<ll,ll> dfs(ll node, ll dep, ll kol) {
map<ll,ll>r;
r[kol] = dep;
if ( visited[node] ) {
return r;
}
visited[node] = 1;
for (auto u : al[node]) {
if ( visited[u.fi] ) continue;
map<ll,ll>t = dfs(u.fi, dep+1, kol + u.se);
if ( t.size() > r.size() ) swap(t,r);
for (auto k:t) {
if ( r.find(k.fi) != r.end() ) {
r[k.fi] = min(r[k.fi], k.se);
}
else {
r[k.fi] = k.se;
}
}
}
if ( r.find(kol+K) != r.end() )
res = min(res, r[kol+K] - dep);
//cout << node << ' ' << dep << ' '<< kol << endl;
return r;
}
int best_path(int n, int k, int h[][2], int l[])
{
K = k;
for (int i = 0 ; i < n-1 ; i++ ) {
al[h[i][0]].pb({h[i][1],l[i]});
al[h[i][1]].pb({h[i][0],l[i]});
}
for (int i = 0; i < n ; i++ ) {
if ( al[i].size() == 1 ) {
dfs(i,0,0);
break;
}
}
if ( res == INT_MAX) return -1;
return res;
}
