#include <bits/stdc++.h>
using namespace std;
int subtask_1(int n, int k, int v1[][2], int *v2){
int psum[n+1];
psum[0]=0;
for (int i=1; i<=n; i++)psum[i]=psum[i-1]+v2[i-1];
long long bst_ans=n+5;
for (long long i=1; i<=n; i++)
for (long long j=1; j<=n; j++)
if (psum[j]-psum[i]==k)bst_ans=min(bst_ans,j-i);
if (bst_ans==n+5)bst_ans=-1;
return bst_ans;
}
vector<pair<int,int>> v[1005];
int visited[1005];
pair<int,int> dp[1005][1005];
void dfs(int i, int tar, int sm, int cnt){
if (visited[i]==0){
visited[i]=1;
dp[tar][i].first=sm;
dp[tar][i].second=cnt;
for (int j=0; j<v[i].size(); j++){
dfs(v[i][j].first,tar,sm+v[i][j].second,cnt+1);
}
}
}
int subtask_2(int n, int k, int v1[][2], int *v2){
int mn_ans=n+5;
for (int i=0; i<n; i++){dp[i][i].first=0;dp[i][i].second=0;}
for (int i=0; i<n-1; i++){
v[v1[i][0]].push_back({v1[i][1],v2[i]});
v[v1[i][1]].push_back({v1[i][0],v2[i]});
}
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
visited[j]=0;
}
dfs(i,i,0,0);
}
for (int i=0; i<n; i++){
for (int j=0; j<n; j++){
if (dp[i][j].first==k){mn_ans=min(mn_ans,dp[i][j].second);}
}
}
if (mn_ans==n+5){mn_ans=-1;}
return mn_ans;
}
int best_path(int n, int k, int v1[][2], int *v2){
int sbtsk_1=1;
for (int i=0; i<n-1; i++){
if (v1[i][0]!=v1[i][1]-1){
sbtsk_1=0;
}
}
if (sbtsk_1){
return(subtask_1(n,k,v1,v2));
}
else if (n<=1000 && k<=1000000){
return(subtask_2(n,k,v1,v2));
}
return -1;
}
