#include <bits/stdc++.h>
#include "race.h"
#define va first //정점
#define vb second //비용
using namespace std;
typedef pair<int,int> pii;
const int mxn = 200005, mxk = 1e6 + 5, inf = 1e9;
vector<pii> G[mxn];
int clk_dfs, clk_dnc;
int cnt[mxn], vis[mxn], par[mxn];
int del[mxn];
int dep[mxn];
int min_cnt[mxk], min_cnt_chk[mxk];
pii Q[mxn];
int q_f, q_r;
int N, K;
int ans = inf;
void dfsi(int v){
cnt[v] = 1;
vis[v] = clk_dfs;
for(pii &p : G[v]){
if(del[p.va] || vis[p.va] == clk_dfs) continue;
dfsi(p.va);
par[p.va] = v;
cnt[v] += cnt[p.va];
}
}
int get_cen(int v, int sz){
for(pii &p : G[v]){
if(del[p.va] || p.va == par[v]) continue;
if(cnt[p.va] > sz/2) return get_cen(p.va, sz);
}
return v;
}
void dfs_race(int v, int sum){
vis[v] = clk_dfs;
Q[q_r++] = {sum, dep[v]}; //va = cost, vb = dep;
for(pii &p : G[v]){
if(del[p.va] || vis[p.va] == clk_dfs) continue;
par[p.va] = v;
dep[p.va] = dep[v] + 1;
dfs_race(p.va, sum + p.vb);
}
}
void dnc(int root){
pii tmp;
++clk_dfs;
dfsi(root);
int cen = get_cen(root, cnt[root]);
min_cnt[0] = 0; min_cnt_chk[0] = ++clk_dnc; //centroid itself!
for(pii &p : G[cen]){
if(del[p.va]) continue;
q_f = q_r = 0;
dep[p.va] = 1;
vis[cen] = ++clk_dfs;
dfs_race(p.va, p.vb);
for(int i = q_f; i < q_r; i++){
if(Q[i].va > K) continue;
if(min_cnt_chk[K - Q[i].va] == clk_dnc){
ans = min(ans, Q[i].vb + min_cnt[K - Q[i].va]);
}
}
while(q_f != q_r){
tmp = Q[q_f++];
if(tmp.va > K) continue;
if(min_cnt_chk[tmp.va] != clk_dnc || min_cnt[tmp.va] > tmp.vb){
min_cnt_chk[tmp.va] = clk_dnc;
min_cnt[tmp.va] = tmp.vb;
}
}
}
del[cen] = 1;
for(pii &p : G[cen]){
if(del[p.va]) continue;
dnc(p.va);
}
}
int best_path(int n, int k, int H[][2], int L[]){
N = n;
K = k;
for(int i = 0; i < n-1; i++){
G[H[i][0]].emplace_back(H[i][1], L[i]);
G[H[i][1]].emplace_back(H[i][0], L[i]);
}
dnc(1);
return ans == inf ? -1 : ans;
}
