#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define MAX_N 200000
#define MAX_K 1000000
struct edge{int u,c;};
typedef vector<edge> vec;
typedef vector<vec> mat;
mat path;
int n,comet,SubSz[MAX_N],MaxSz[MAX_N];
bool killed[MAX_N];
bool chk[MAX_N];
vector<int> s;
int dfs(int v){
chk[v]=1;
s.push_back(v);
int ret=0;
SubSz[v]=MaxSz[v]=1;
for(int i=0;i<path[v].size();i++){
int u=path[v][i].u;
if(killed[u]||chk[u])continue;
ret=dfs(u);
SubSz[v]+=ret;
MaxSz[v]=max(MaxSz[v],ret+1);
}
chk[v]=0;
return SubSz[v];
}
int centroid(int v){
//printf("centroid %d\n",v);
s.clear();
dfs(v);
int x,ret=v,Max=0;
for(int i=0;i<s.size();i++){
x=s[i];
//printf("%d : %d %d\n",x,MaxSz[x],SubSz[x]);
if(Max<min(SubSz[v]-MaxSz[x],MaxSz[x])){
Max=min(SubSz[v]-MaxSz[x],MaxSz[x]);
ret=x;
}
}
return ret;
}
int stamp[MAX_K+1],a[MAX_K+1];
struct state{int v,c,len;};
int f(int v){
//printf("%d \n",v);
//for(int i=0;i<n;i++)printf("%d,%d ",killed[i],chk[i]);
//puts("");
int root=centroid(v);
killed[root]=1;
//printf("root=%d\n",root);
int ret=1e9;
for(int i=0;i<path[root].size();i++){
int u=path[root][i].u;
if(killed[u])continue;
//printf("u=%d\n",u);
queue<state> Q;
Q.push(state{u,path[root][i].c,1});
chk[u]=1;
while(!Q.empty()){
state h=Q.front();
Q.pop();
if(h.c==comet)ret=min(ret,h.len);
if(h.c>=comet)continue;
if(stamp[comet-h.c]==root)ret=min(ret,a[comet-h.c]+h.len);
for(int j=0;j<path[h.v].size();j++){
int uu=path[h.v][j].u;
if(killed[uu]||chk[uu])continue;
chk[uu]=1;
Q.push(state{uu,h.c+path[h.v][j].c,h.len+1});
}
}
Q.push(state{u,path[root][i].c,1});
chk[u]=0;
while(!Q.empty()){
state h=Q.front();
Q.pop();
if(h.c>=comet)continue;
if(stamp[h.c]==root)
a[h.c]=min(a[h.c],h.len);
else
stamp[h.c]=root,a[h.c]=h.len;
for(int j=0;j<path[h.v].size();j++){
int uu=path[h.v][j].u;
if(killed[uu]||chk[uu]==0)continue;
chk[uu]=0;
Q.push(state{uu,h.c+path[h.v][j].c,h.len+1});
}
}
}
for(int i=0;i<path[root].size();i++){
int u=path[root][i].u;
if(killed[u])continue;
ret=min(ret,f(u));
}
killed[root]=0;
return ret;
}
int best_path(int N, int K, int H[][2], int L[]){
memset(stamp,-1,sizeof(stamp));
n=N;
comet=K;
path.assign(n,vec());
for(int i=0;i<n;i++){
path[H[i][0]].push_back(edge{H[i][1],L[i]});
path[H[i][1]].push_back(edge{H[i][0],L[i]});
}
int ret=f(0);
return ret==1e9?-1:ret;
}
