#include <bits/stdc++.h>
#include "race.h"
using namespace std;
void depth(vector<pair<int, int>> adj[], int u, int e, vector<int> &cnt)
{
for(auto v: adj[u])
{
if(v.first!=e)
{
cnt[v.first] = cnt[u]+v.second;
depth(adj, v.first, u, cnt);
}
}
}
void all_pairs_distance(vector<pair<int, int>> adj[], int N, vector<vector<int>> &cnt)
{
for(int i = 0; i<N; i++)
{
vector<int> temp(N);
depth(adj, i, -1, temp);
cnt.push_back(temp);
}
}
void depth2(vector<pair<int, int>> adj[], int u, int e, vector<int> &cnt)
{
for(auto v: adj[u])
{
if(v.first!=e)
{
cnt[v.first] = cnt[u]+1;
depth2(adj, v.first, u, cnt);
}
}
}
void all_pairs_distance2(vector<pair<int, int>> adj[], int N, vector<vector<int>> &cnt)
{
for(int i = 0; i<N; i++)
{
vector<int> temp(N);
depth2(adj, i, -1, temp);
cnt.push_back(temp);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
vector<pair<int, int>> adj[N];
for(int i = 0; i<N-1; i++)
{
adj[H[i][0]].push_back(make_pair(H[i][1], L[i]));
adj[H[i][1]].push_back(make_pair(H[i][0], L[i]));
}
vector<vector<int>> cnt;
all_pairs_distance(adj, N, cnt);
vector<vector<int>> cnt2;
all_pairs_distance2(adj, N, cnt2);
bool flag = false;
int res = 1e8;
for(int i = 0; i<N; i++)
{
for(int j = 0; j<N; j++)
{
if(cnt[i][j]==K)
res = min(res, cnt2[i][j]), flag = true;
}
}
if(!flag)
return -1;
return res;
}
