#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define N 200005
const int INF = 1e9 + 7;
vector <int> nodes;
int dpt[N], types[N], mx = 1e9, rem[N], sub[N];
ll baha[N];
vector <pair <int, int>> v[N], G[N];
int p[1000005];
void dfs (int x, int pr) {
sub[x] = 1;
for (auto i : v[x]) {
if (i.ff == pr or rem[i.ff]) {
continue;
}
dfs (i.ff, x);
sub[x] += sub[i.ff];
}
}
int centroid (int x, int pr, int san) {
for (auto i : v[x]) {
if (i.ff == pr or rem[i.ff]) continue;
if (sub[i.ff] > san / 2) {
return centroid (i.ff, x, san);
}
}
return x;
}
void solve (int x, int pr, ll val, int type, int edge) {
// cout << x << " " << val << " " << type << " " << edge << endl;
baha[x] = val;
types[x] = type;
dpt[x] = edge;
nodes.pb (x);
for (auto i : v[x]) {
if (i.ff == pr or rem[i.ff]) continue;
solve (i.ff, x, val + i.ss, type, edge + 1);
}
}
void build (int x, int pr, int k) {
int centr = centroid (x, -1, sub[x]); // centr tapdyk
rem[centr] = 1;
int at = 0;
nodes.clear();
for (auto i : v[centr]) {
if (rem[i.ff]) continue;
solve (i.ff, 0, i.ss, ++at, 1);
}
for (int i : nodes) {
G[types[i]].pb ({baha[i], dpt[i]});
}
for (int i = 1; i <= at; ++i) {
for (auto j : G[i]) {
if (j.ff <= k) {
mx = min (mx, p[k - j.ff] + j.ss);
}
}
for (auto j : G[i]) {
if (j.ff <= k) {
p[j.ff] = min (p[j.ff], j.ss);
}
}
G[i].clear();
}
for (int i : nodes) if (baha[i] <= k) p[baha[i]] = INF;
for (auto i : v[centr]) {
if (rem[i.ff]) {
continue;
}
dfs (i.ff, -1);
build (i.ff, centr, k);
}
}
int best_path(int n, int k, int h[][2], int l[]) {
for (int i = 1; i <= k; ++i) p[i] = INF;
for (int i = 0; i < n - 1; ++i) {
int u = h[i][0], vv = h[i][1], w = l[i];
v[u].pb ({vv, w});
v[vv].pb ({u, w});
}
dfs (0, -1);
build (0, -1, k);
if (mx == 1e9) mx = -1;
return mx;
}
//#define MAX_N 500000
//int n, k;
//int h[MAX_N][2];
//int l[MAX_N];
//
//int main() {
// freopen ("input.txt", "r", stdin);
// cin >> n >> k;
// for(int i = 0; i < n-1; i++)
// cin >> h[i][0] >> h[i][1] >> l[i];
// int ans;
// ans = best_path(n,k,h,l);
// cout << ans << "\n";
// return 0;
//}
