#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back
vector<pii> g[200005];
bool vis[200005];
int sub[200005];
int nn = 0;
int ans = 1e9;
void dfs1(int u, int p){
sub[u] = 1;
nn++;
for(int i=0;i<g[u].size();i++){
int v = g[u][i].fi;
if(v == p || vis[v]) continue;
dfs1(v, u);
sub[u] += sub[v];
}
}
int dfs2(int u, int p){
for(int i=0;i<g[u].size();i++){
int v = g[u][i].fi;
if(v == p || vis[v]) continue;
if(sub[v] > nn/2) return dfs2(v, u);
}
return u;
}
int best[1000005];
vector<pii> val;
void dfs3(int u, int p, int d, int c, int k){
if(c > k) return;
if(best[k-c] != -1) ans = min(ans, best[k-c] + d);
val.eb(mp(c, d));
for(int i=0;i<sz(g[u]);i++){
int v = g[u][i].fi, w = g[u][i].se;
if(v == p || vis[v]) continue;
dfs3(v, u, d+1, c+w, k);
}
}
void decompose(int u, int p, int k){
nn = 0;
dfs1(u, 0);
int centroid = dfs2(u, 0);
vis[centroid] = 1;
vector<int> dist;
best[0] = 0;
dist.eb(0);
for(int i=0;i<sz(g[centroid]);i++){
int v = g[centroid][i].fi, w = g[centroid][i].se;
if(v == p || vis[v]) continue;
val.clear();
dfs3(v, centroid, 1, w, k);
for(int j=0;j<sz(val);j++){
if(best[val[j].fi] == -1 || best[val[j].fi] > val[j].se) best[val[j].fi] = val[j].se;
dist.eb(val[j].fi);
}
}
for(int i=0;i<sz(dist);i++){
best[dist[i]] = -1;
}
for(int i=0;i<g[centroid].size();i++){
int v = g[centroid][i].fi;
if(v == p || vis[v]) continue;
decompose(v, centroid, k);
}
}
int best_path(int n, int k, int h[][2], int l[]){
for(int i=0;i<n-1;i++){
g[h[i][0]].eb(mp(h[i][1], l[i]));
g[h[i][1]].eb(mp(h[i][0], l[i]));
}
memset(best, -1, sizeof(best));
decompose(0, -1, k);
if(ans == 1e9) ans = -1;
return ans;
}
