#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#endif
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
vector<vector<pair<int, int>>> adj;
vector<int> blocked;
int best = INT32_MAX;
int k;
struct Tree
{
int n = 0;
int centroid = -1;
void spread(int i, int p = -1)
{
n++;
for (auto [c, D] : adj[i])
{
if (c != p && !blocked[c])
{
spread(c, i);
}
}
}
int find_centroid(int i, int p = -1)
{
int subtree_size = 1;
int largest_subtree = 0;
for (auto [c, D] : adj[i])
{
if (c != p && !blocked[c])
{
int sub = find_centroid(c, i);
subtree_size += sub;
largest_subtree = max(largest_subtree, sub);
}
}
if (largest_subtree <= n / 2 && n - subtree_size <= n / 2)
centroid = i;
return subtree_size;
}
void dfs(int i, vector<pair<int, int>> &out, int d = 0, int depth = 0, int p = -1)
{
out.push_back({d, depth});
for (auto [c, D] : adj[i])
{
if (c != p && !blocked[c])
{
dfs(c, out, d + D, depth + 1, i);
}
}
}
vector<int> split()
{
if (centroid == -1)
return {};
blocked[centroid] = true;
vector<int> out;
for (auto [c, d] : adj[centroid])
{
if (!blocked[c])
out.push_back(c);
}
return out;
}
Tree(int start)
{
spread(start);
if (n > 1)
{
find_centroid(start);
assert(centroid != -1);
multiset<pair<int, int>> all;
all.insert({0, 0});
for (auto [c, d] : adj[centroid])
{
if (blocked[c])
continue;
vector<pair<int, int>> blub;
dfs(c, blub, d, 1, centroid);
for (auto &[a, b] : blub)
{
int other = k - a;
auto ptr = all.lower_bound({other, 0});
if (ptr != all.end() && ptr->first == other)
{
int new_one = b + ptr->second;
best = min(best, new_one);
}
}
for (auto x : blub)
all.insert(x);
}
}
}
};
#ifndef _DEBUG
#include "race.h"
#else
int best_path(int N, int K, int H[][2], int L[]);
#endif
int best_path(int N, int K, int H[][2], int L[])
{
adj.resize(N);
blocked.resize(N);
k = K;
for (int i = 0; i < N - 1; i++)
{
adj[H[i][1]].push_back(pair<int, int>{H[i][0], L[i]});
adj[H[i][0]].push_back(pair<int, int>{H[i][1], L[i]});
}
vector<int> todo = {0};
while (todo.size() && todo.size() != N - 1)
{
int i = todo.back();
todo.pop_back();
Tree tree(i);
if (tree.n > 1)
for (int x : tree.split())
todo.push_back(x);
}
if (best == INT32_MAX)
return -1;
return best;
}
#ifdef _DEBUG
#define MAX_N 500000
static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;
inline void my_assert(int e)
{
if (!e)
abort();
}
void read_input()
{
int i;
my_assert(2 == scanf("%d %d", &N, &K));
for (i = 0; i < N - 1; i++)
my_assert(3 == scanf("%d %d %d", &H[i][0], &H[i][1], &L[i]));
my_assert(1 == scanf("%d", &solution));
}
signed main()
{
freopen("/home/elias/Downloads/ioi2011tests/race-test/subtask4/grader.in.13", "r", stdin);
cin.tie(0);
ios_base::sync_with_stdio(false);
int ans;
read_input();
ans = best_path(N, K, H, L);
if (ans == solution)
printf("Correct.\n");
else
printf("Incorrect. Returned %d, Expected %d.\n", ans, solution);
return 0;
}
#endif
