//pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "race.h"
const int sz=1001,INF=1000000000;
using namespace std;
int res;
vector<int>d(sz);
vector<bool>isSeen(sz);
vector<vector<int>>parent(sz,vector<int>(11)),cnts(sz,vector<int>(sz,0)),dist(sz,vector<int>(sz,INF));
vector<vector<pair<int,int>>>nums;
void dfs(int num)
{
isSeen[num]=true;
for(int i=0;i<nums[num].size();i++)
{
if(!isSeen[nums[num][i].first])
{
parent[nums[num][i].first][0]=num,d[nums[num][i].first]=d[num]+1;
dfs(nums[num][i].first);
}
}
}
int lca(int num1,int num2)
{
if(d[num1]<d[num2])
{
swap(num1,num2);
}
for(int i=10;i>=0;i--)
{
if(d[num1]-pow(2,i)>=d[num2])
{
num1=parent[num1][i];
}
}
if(num1==num2)
{
return num1;
}
else
{
for(int i=10;i>=0;i--)
{
if(parent[num1][i]!=parent[num2][i])
{
num1=parent[num1][i],num2=parent[num2][i];
}
}
return parent[num1][0];
}
}
void bfs(int num)
{
queue<int>numS;
numS.push(num);
cnts[num][num]=1;
while(numS.size()!=0)
{
res=numS.front();
numS.pop();
for(int i=0;i<nums[res].size();i++)
{
if(cnts[num][nums[res][i].first]==0)
{
numS.push(nums[res][i].first);
cnts[num][nums[res][i].first]=cnts[num][res]+1;
}
}
}
}
void dijkstra(int num)
{
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>Pq;
Pq.push({0,num});
dist[num][num]=0;
while(Pq.size()!=0)
{
res=Pq.top().second;
Pq.pop();
for(int i=0;i<nums[res].size();i++)
{
if(dist[num][res]+nums[res][i].second<dist[num][nums[res][i].first])
{
Pq.push({dist[num][nums[res][i].first],nums[res][i].first});
dist[num][nums[res][i].first]=dist[num][res]+nums[res][i].second;
}
}
}
}
int best_path(int n,int m,int nums1[][2],int nums2[])
{
int anc,cnt,Dist,ans=INF;
nums.resize(n+1);
for(int i=0;i<n-1;i++)
{
nums[nums1[i][0]+1].push_back({nums1[i][1]+1,nums2[i]}),nums[nums1[i][1]+1].push_back({nums1[i][0]+1,nums2[i]});
}
dfs(1);
for(int i=1;i<=10;i++)
{
for(int j=1;j<=n;j++)
{
parent[j][i]=parent[parent[j][i-1]][i-1];
}
}
for(int i=1;i<=n;i++)
{
bfs(i),dijkstra(i);
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
anc=lca(i,j),Dist=dist[anc][i]+dist[anc][j],cnt=cnts[anc][i]+cnts[anc][j]-1;
if(Dist==m)
{
ans=min(ans,cnt-1);
}
}
}
if(ans==INF)
{
ans=-1;
}
return ans;
}
