#include "race.h"
#include <bits/stdc++.h>
using namespace std;
int k;
typedef long long ll;
vector <int> ctree[1000005];
vector <pair <int, int>> graf[1000005];
bool visited[1000005];
bool bio[1000005];
int sz[1000005];
int dist[1000005];
int grane[1000005];
stack <int> qq;
int prvi;
void dfs1(int v){
sz[v] = 1;
visited[v] = 1;
for(auto par : graf[v]){
int c = par.first;
if(!bio[c] && !visited[c]){
dfs1(c);
sz[v] += sz[c];
}
}
visited[v] = 0;
}
int nadji(int v, int n, int par){
for(auto pr : graf[v]){
int c = pr.first;
if(bio[c]) continue;
if(c == par) continue;
if(sz[c] > n/2) return nadji(c, n, v);
}
return v;
}
int mnn1[1000005];
int mnn2[1000005];
struct strukt{
int first;
int second;
int third;
};
const int INF = 1000001;
int res = INF;
vector <strukt> sons[1000005];
void dfs2(int v, int dis, int brg, int root){
visited[v] = 1;
if(v != root) sons[root].push_back({dis, brg, v});
for(auto pr : graf[v]){
int c = pr.first;
int x = pr.second;
if(!visited[c] && !bio[c]){
dfs2(c, min(INF, dis+x), brg+1, root);
}
}
visited[v] = 0;
}
void decompose(){
queue <pair <int, int>> q;
q.push({1, 0});
while(!q.empty()){
int v = q.front().first;
int parent = q.front().second;
q.pop();
dfs1(v);
v = nadji(v, sz[v], 0);
bio[v] = 1;
dfs2(v, 0, 0, v);
if(!parent) prvi = v;
else{
ctree[parent].push_back(v);
}
qq.push(v);
for(auto pr : graf[v]){
int c = pr.first;
if(!bio[c]){
q.push({c, v});
}
}
}
}
void dfs3(){
vector <int> vec[1000005];
while(!qq.empty()){
int cnt = 0;
int v = qq.top();
qq.pop();
for(auto c : ctree[v]){
sons[c].push_back({0, 0, c});
cnt++;
for(auto pr : sons[c]) vec[cnt].push_back(pr.third);
sons[c].clear();
}
for(auto pr : sons[v]){
int a = pr.first;
int b = pr.second;
int c = pr.third;
dist[c] = a;
grane[c] = b;
}
for(int i=1; i<=cnt; i++){
for(auto gg : vec[i]){
int a = dist[gg];
int b = grane[gg];
if(a == k) res = min(res, b);
else if(a < k){
res = min(res, b + mnn1[k-a]);
}
}
for(auto gg : vec[i]){
int a = dist[gg];
int b = grane[gg];
if(a > k) continue;
if(mnn1[a] >= b){
mnn2[a] = mnn1[a];
mnn1[a] = b;
}
else if(mnn2[a] > b){
mnn2[a] = b;
}
}
vec[i].clear();
}
for(auto pr : sons[v]){
if(pr.first > k) continue;
mnn1[pr.first] = mnn2[pr.first] = INF;
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
int n = N;
k = K;
for(int i=0; i<n-1; i++){
int a = H[i][0] + 1;
int b = H[i][1] + 1;
graf[a].push_back({b, L[i]});
graf[b].push_back({a, L[i]});
}
decompose();
for(int i=1; i<=n; i++) graf[i].clear();
for(int i=1; i<=1000000; i++){
mnn1[i] = mnn2[i] = INF;
}
dfs3();
if(res == INF) return -1;
return res;
}
