#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_map>
#include "race.h"
using namespace std;
const int n = 200003;
int s, k;
vector<pair<int, int>> g[n];
long long h[n];
int d[n];
bool mark[n];
int ans = -1;
void answer(int x)
{
if (ans == -1)
ans = x;
else
ans = min(ans, x);
}
void calc_height(int v, int p)
{
d[v] = 1;
for (pair<int, int> to : g[v])
{
if (to.first == p || mark[to.first])
continue;
h[to.first] = h[v] + to.second;
calc_height(to.first, v);
d[v] += d[to.first];
}
}
int center(int v, int p, int sz)
{
int t = -1;
for (pair<int, int> to : g[v])
{
if (mark[to.first] || to.first == p)
continue;
if (d[to.first] > sz / 2)
{
t = to.first;
break;
}
}
return t == -1 ? v : center(t, v, sz);
}
void get_all(int v, int p, vector<pair<long long, int>>& st, long long dp, int l)
{
st.push_back({ dp, l });
for (auto to : g[v])
{
if (to.first == p || mark[to.first])
continue;
get_all(to.first, v, st, dp + to.second, l + 1);
}
}
void solve(int v)
{
//cout << v;
calc_height(v, -1);
v = center(v, -1, d[v]);
mark[v] = true;
calc_height(v, -1);
map<long long, int> st;
for (auto to : g[v])
{
if (mark[to.first])
continue;
vector<pair<long long, int>> dst;
get_all(to.first, v, dst, to.second, 1);
for (auto x : dst)
{
if (x.first > k)
continue;
if (x.first == k)
answer(x.second);
else if (st.count(k - x.first))
answer(x.second + st[k - x.first]);
}
for (auto x : dst)
st[x.first] = x.second;
solve(to.first);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
s = N;
k = K;
for (int i = 0; i < s - 1; i++)
{
int a, b, l;
a = H[i][0];
b = H[i][1];
l = L[i];
g[a].push_back({ b, l });
g[b].push_back({ a, l });
}
solve(0);
return ans;
}
