#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
vector <pair <int, long long> > v[maxn];
map <long long, int> m[maxn];
map <long long, int> ::iterator it;
long long dist[maxn];
int koraci[maxn];
int ans = 1e9, parent[maxn];
int find (int x){
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
void unite (int x, int y, int lca, int k){
//cout << "unite " << x << " " << y << " " << lca << " " << k << endl;
if (m[x].size() < m[y].size()) swap(x, y);
parent[y] = x;
/*
cout << "cvor " << y << endl;
for (auto i : m[y]){
cout << i.first << " " << i.second << endl;
}
cout << "cvor " << x << endl;
for (auto i : m[x]){
cout << i.first << " " << i.second << endl;
}
cout << endl;
*/
for (auto i : m[y]){
it = m[x].find(k + 2 * dist[lca] - i.first);
if (it != m[x].end()) ans = min(ans, m[x][k + 2 * dist[lca] - i.first] + i.second - 2 * koraci[lca]);
}
for (auto i : m[y]){
if (m[x][i.first] == 0 or (m[x][i.first] > i.second)) m[x][i.first] = i.second;
}
m[y].clear();
}
void dfs (int x, int p, long long k){
for (int i = 0; i < v[x].size(); i++){
int y = v[x][i].first;
if (y != p){
dfs(y, x, k);
//cout << "spajam " << x << " " << y << endl;
int px = find(x);
int py = find(y);
unite(px, py, x, k);
}
}
}
void dfs2 (int x, int p){
for (int i = 0; i < v[x].size(); i++){
int y = v[x][i].first;
int d = v[x][i].second;
if (y != p){
dist[y] = dist[x] + d;
koraci[y] = koraci[x] + 1;
dfs2(y, x);
}
}
}
int best_path (int n, int k, int h[maxn][2], int l[maxn]){
for (int i = 0; i < n - 1; i++){
v[h[i][0]].push_back({h[i][1], l[i]});
v[h[i][1]].push_back({h[i][0], l[i]});
}
dist[0] = 0, koraci[0] = 1;
dfs2(0, 0);
for (int i = 0; i < n; i++) m[i][dist[i]] = koraci[i], parent[i] = i;
dfs(0, 0, k);
if (ans == 1e9) return -1;
else return ans;
}
/*
int main (void){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, k, h[maxn][2], l[maxn];
cin >> n >> k;
for (int i = 0; i < n - 1; i++) cin >> h[i][0] >> h[i][1] >> l[i];
cout << best_path(n, k, h, l) << endl;
return 0;
}
*/
