#include "race.h"
#include <vector>
#include <iostream>
using namespace std;
const long long MAX = 1E16;
vector<pair<int,int> > adj[200020];
long long current = 0;
long long len = 0;
long long best = MAX;
long long k;
long long n;
void dfs(int node, int parent) {
if(current >= k) {
if (current == k) {
best = min(len,best);
}
return;
}
for(auto [child, cost] : adj[node]) {
if(child == parent) continue;
current += cost;
len++;
dfs(child, node);
len--;
current -= cost;
}
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
for (int i = 0; i < N-1; i++){
adj[H[i][0]].emplace_back(H[i][1],L[i]);
adj[H[i][1]].emplace_back(H[i][0],L[i]);
}
for(int i = 0; i < N; i++) {
current = 0;
len = 0;
dfs(i,i);
}
return (best == MAX) ? -1 : best;
}
