#include "race.h"
using namespace std;
#include <bits/stdc++.h>
const int NMAX = 200000;
#define int long long
vector<pair<int, int>> chemins[NMAX];
struct T {
int longueur, noeud, nbAretesPrises;
T(int _1, int _2, int _3)
{
longueur = _1; noeud = _2; nbAretesPrises = _3;
}
bool operator<(const T & other) const {
return longueur > other.longueur;
}
};
#undef int
int dejaVu[NMAX];
int best_path(int N, int K, int H[][2], int L[])
{
#define int long long
for(int iC = 0; iC < N-1; iC++)
{
int a = H[iC][0], b = H[iC][1], longueur = L[iC];
chemins[a].push_back({b, longueur});
chemins[b].push_back({a, longueur});
}
int meill = NMAX;
for(int iNoeud = 0; iNoeud < N; iNoeud++)
{
priority_queue<T> plusCourtNoeud;
plusCourtNoeud.push(T(0, iNoeud, 0));
while(plusCourtNoeud.size())
{
auto cas = plusCourtNoeud.top();
plusCourtNoeud.pop();
if(dejaVu[cas.noeud] == iNoeud+1) continue;
if(cas.longueur > K) break;
if(cas.longueur == K)
{
meill = min(meill, cas.nbAretesPrises);
continue;
}
dejaVu[cas.noeud] = iNoeud+1;
for(auto pro : chemins[cas.noeud])
{
plusCourtNoeud.push(T(cas.longueur+pro.second, pro.first, cas.nbAretesPrises+1));
}
}
}
if(meill == NMAX) meill = -1;
return meill;
}
