#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define x first
#define y second
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define MP make_pair
typedef long long ll;
typedef double db;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<db, db> pdd;
typedef pair<ll, ll> pll;
typedef vector<int> VI;
typedef vector<ll> VL;
const int INF = 1e9 + 47;
const int MAXN = 2e5 + 47;
vector<pii> g[MAXN];
int siz[MAXN];
bool usedC[MAXN];
int n, k, ans = INF;
int dfsSZ(int v, int par)
{
siz[v] = 1;
for (auto [to, w] : g[v])
{
if (to != par && !usedC[to])
siz[v] += dfsSZ(to, v);
}
return siz[v];
}
void dfs2(int v, int par, ll dist, int ed, vector<array<ll, 3>>& comp)
{
comp.pb({v, dist, ed});
for (auto [to, w] : g[v])
{
if (to == par || usedC[to])
continue;
dfs2(to, v, dist + w, ed + 1, comp);
}
}
void build(int u)
{
dfsSZ(u, -1);
int szAll = siz[u];
int pr = u;
while (true)
{
int v = -1;
for (auto [to, w] : g[u])
{
if (to == pr || usedC[to])
continue;
if (siz[to] * 2 > szAll)
{
v = to;
break;
}
}
if (v == -1)
break;
pr = u;
u = v;
}
int cent = u;
usedC[cent] = true;
vector<vector<array<ll, 3>>> ar;
map<ll, multiset<int>> mp;
mp[0].insert(0);
for (auto [to, w] : g[cent])
{
if (usedC[to])
continue;
vector<array<ll, 3>> cur;
dfs2(to, cent, w, 1, cur);
ar.pb(cur);
for (const auto& [v, dist, ed]: cur)
mp[dist].insert(ed);
}
for (const auto& vec: ar)
{
for (const auto& [v, dist, ed]: vec)
mp[dist].erase(mp[dist].find(ed));
for (const auto& [v, dist, ed]: vec)
{
if (mp.count(k - dist) && !mp[k - dist].empty())
ans = min(ans, *mp[k - dist].begin() + (int)ed);
}
for (const auto& [v, dist, ed]: vec)
mp[dist].insert(ed);
}
for (auto [to, w] : g[cent])
{
if (!usedC[to])
{
build(to);
}
}
}
int best_path(int N, int K_, int H[][2], int L[])
{
//cin >> N >> K_;
//FOR (i, 0, N - 1)
//cin >> H[i][0] >> H[i][1] >> L[i];
//int trash;
//cin >> trash;
n = N, k = K_;
FOR (i, 0, n - 1)
{
int a = H[i][0], b = H[i][1], d = L[i];
g[a].pb({b, d});
g[b].pb({a, d});
}
build(0);
if (ans == INF)
ans = -1;
return ans;
}
//int H[MAXN][2];
//int L[MAXN];
//int main()
//{
//int a = 0;
//int b = 0;
//cout << best_path(a, b, H, L) << '\n';
//return 0;
//}
