//liem code
#include "race.h"
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_N 200001
#define MAX_K 1000001
const int non = 0x3fffffff;
vector<int> G[MAX_N];
int ex[MAX_N],ey[MAX_N],l[MAX_N],K;
bool forb[MAX_N];
int ts,chk[MAX_N],cut[MAX_N],Q[MAX_N],depth[MAX_N],len[MAX_N],sz[MAX_N],line[MAX_K];
int gety(int x, int i){
return x == ex[i] ? ey[i] : ex[i];
}
int dfs(int x)
{
int head, tail, res = non;
head = tail = -1;
Q[++head] = x; chk[x] = ts; depth[x] = 0;
while (tail < head){
int p = Q[++tail];
for (int i=0;i<G[p].size();i++) if (!forb[G[p][i]]){
int q = gety(p,G[p][i]);
if (chk[q] != ts){
Q[++head] = q;
chk[q] = ts;
depth[q] = depth[p] + 1;
}
}
}
ts++;
int all = head + 1;
if (all > 1){
int c = x;
for (int j=head;j>=0;j--){
int p = Q[j];
sz[p] = 1;
bool good = true;
for (int i=0;i<G[p].size();i++) if (!forb[G[p][i]]){
int q = gety(p,G[p][i]);
if (depth[p] < depth[q]){
sz[p] += sz[q];
if (sz[q] > all/2) good = false;
}
}
if (all - sz[p] > all/2) good = false;
if (good){
c = p;
break;
}
}
int child = 0;
head = tail = 0; x = c;
Q[0] = x; chk[x] = ts; depth[x] = len[x] = 0; line[0] = 0;
for (int i=0;i<G[x].size();i++) if (!forb[G[x][i]]){
int y = gety(x,G[x][i]);
cut[child++] = y;
chk[y] = ts;
depth[y] = 1;
len[y] = l[G[x][i]];
}
for (int s=0;s<child;s++){
int last = head;
if (len[cut[s]] <= K) Q[++head] = cut[s];
while (tail < head){
int p = Q[++tail];
res = min(res,line[K-len[p]]+depth[p]);
for (int i=0;i<G[p].size();i++) if (!forb[G[p][i]]){
int q = gety(p,G[p][i]);
if (chk[q] != ts){
chk[q] = ts;
depth[q] = depth[p] + 1;
len[q] = len[p] + l[G[p][i]];
if (len[q] <= K) Q[++head] = q;
}
}
}
for (int j=last+1;j<=head;j++){
int p = Q[j];
line[len[p]] = min(line[len[p]],depth[p]);
}
}
for (int j=0;j<=head;j++){
line[len[Q[j]]] = non;
}
ts++;
for (int i=0;i<G[x].size();i++) if (!forb[G[x][i]]){
forb[G[x][i]] = 1;
int small = dfs(gety(c,G[x][i]));
res = min(res,small);
}
}
return res;
}
int best_path(int N, int K_, int H[][2], int L[])
{
K = K_;
for (int i=0;i<N-1;i++){
int x = H[i][0], y = H[i][1];
G[x].push_back(i);
G[y].push_back(i);
ex[i] = x; ey[i] = y; l[i] = L[i];
}
for (int i=0;i<N;i++) chk[i] = -1;
for (int i=0;i<=K;i++) line[i] = non;
int ans = dfs(0);
if (ans == non) ans = -1;
return ans;
}
