#pragma GCC optimize("Ofast")
#pragma GCC optimize ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
// #define ll long long
#define pb push_back
#define endl '\n'
#define ff first
#define ss second
typedef vector<int> vii;
typedef pair<int,int> pii;
const int inf = INT_MAX;
const int N = 2e5 + 5;
int n,k,a,b,c;
int sz[N],fix[N],dead[N];
vector <vector<pii>> v(N);
int s,u;
int len;
vector <vii> lst(N);
int ans;
vector <int> A;
void dfs(int x) {
sz[x] = 1;
fix[x] = 1;
for (auto to:v[x]) {
if (!fix[to.ff] && !dead[to.ff]) {
dfs(to.ff);
sz[x] += sz[to.ff];
}
}
}
void dfs1(int x) {
s++;
fix[x] = 1;
for (auto to:v[x]) {
if (!dead[to.ff] && !fix[to.ff]) {
dfs1(to.ff);
}
}
}
int dfs2(int x, int p) {
for (auto to:v[x]) {
if (dead[to.ff] || to.ff == p) continue;
if (sz[to.ff] > s/2) return dfs2(to.ff,x);
}
return x;
}
void dfs3(int x, int p, int len,int d,vector <pii> &lst) {
if (len > k) return;
lst.pb({len,d});
for (auto to:v[x]) {
if (dead[to.ff] || to.ff == p) continue;
dfs3(to.ff,x,len+to.ss,d+1,lst);
}
}
void solve(int u) {
vector<int> tmp;
for (auto lw:v[u]) {
if (dead[lw.ff]) continue;
vector <pii> lst;
dfs3(lw.ff,u,lw.ss,1,lst);
for (auto l:lst) {
if (l.ff > k) continue;
if (A[k-l.ff] != inf) ans = min(ans,l.ss+A[k-l.ff]);
}
for (auto l:lst) {
if (l.ff > k) continue;
A[l.ff] = min(A[l.ff],l.ss);
tmp.pb(l.ff);
}
}
for (auto c:tmp) {
A[c] = inf;
}
}
int best_path(int N, int K, int H[][2], int L[]) {
n=N;
k = K;
for (int i = 0; i < n-1; i++) {
a = H[i][0];
b = H[i][1];
c = L[i];
v[a].pb({b,c});
v[b].pb({a,c});
}
bool ok = true;
ans = inf;
A = vector <int> (k+1,inf);
A[0] = 0;
while (ok) {
ok = false;
for (int i = 0; i < n; i++) {
fix[i] = 0;
sz[i] = 0;
}
for (int i = 0; i < n; i++) {
if (!fix[i] && !dead[i]) dfs(i);
}
for (int i = 0; i < n; i++) {
fix[i] = 0;
}
for (int i = 0; i < n; i++) {
if (!fix[i] && !dead[i]) {
s = 0;
dfs1(i);
u = dfs2(i,-1);
if (s > 1) {
ok = true;
solve(u);
dead[u] = 1;
}
}
}
}
if (ans == inf) ans = -1;
return ans;
}
