#include "race.h"
#include<bits/stdc++.h>
using namespace std ;
int n , k , dis[1001] ;
vector<pair<int , int >> adj[1001];
int vis[1001] , vid ;
int bfs(int s){
memset(dis , 0 , sizeof dis);
queue<pair<int , int > > q ;
q.push({s , 0});
dis[s] = 0 ; vis[s] = vid ;
while(!q.empty()){
auto f = q.front();
q.pop();
for(auto c : adj[f.first]){
if(vis[c.first] == vid)continue ;
int nc = f.second + c.second ;
int nd = dis[f.first] + 1 ;
dis[c.first] = nd ;
vis[c.first] = vid ;
q.push({c.first , nc});
if(nc == k)return nd ;
}
}
return 1e9 ;
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K ;
int mn = 1e9 ;
for(int i = 0 ; i < N ; i ++){
int from = H[i][0] , to = H[i][1];
adj[from].push_back({to , L[i]});
adj[to].push_back({from , L[i]});
}
for(int i = 0 ; i < N ; i ++)
vid ++ , mn = min(mn , bfs(i));
return (mn == 1e9 ? -1 : mn);
}
