#include<bits/stdc++.h>
#include "race.h"
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double
using namespace std;
/*
const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 5;
const ll ROOTN = 320;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;
*/
#define MAXN 200005
#define inf 1000000009
int best_path(int N, int K, int H[][2], int L[]);
vll g[MAXN];
bool centroid_marked[MAXN];
int subtree[MAXN], K, tmpans, ans;
map<ll,int> road, final;
int dfs_init(int a, int par)
{
subtree[a] = 1;
for(pll bb : g[a])
if(bb.ff != par and !centroid_marked[bb.ff])
subtree[a] += dfs_init(bb.ff, a);
return subtree[a];
}
int getCentroid(int a, int par, int n)
{
bool is_centroid = (n - subtree[a] <= n/2);
int hvy = -1;
for(pll bb : g[a])
if(bb.ff != par and !centroid_marked[bb.ff])
{
is_centroid = is_centroid && (subtree[bb.ff] <= n/2);
if(hvy == -1 || subtree[hvy] < subtree[bb.ff]) hvy = bb.ff;
}
if(is_centroid)
return a;
return getCentroid(hvy, a, n);
}
void calc(int a, int par, int dist, int lev)
{
for(pll bb : g[a])
if(bb.ff != par and !centroid_marked[bb.ff])
calc(bb.ff, a, bb.ss + dist, lev+1);
if(road.find(dist) != road.end()) road[dist] = min(road[dist], lev); else road[dist] = lev;
}
void dcmp(int root)
{
final.clear();
final[0] = 0;
tmpans = inf;
int n = dfs_init(root, -1);
int cen = getCentroid(root, -1, n);
centroid_marked[cen] = true;
// cout<<"cen = "<<cen<<"\n";
for(pll bb : g[cen])
if(!centroid_marked[bb.ff])
{
road.clear();
calc(bb.ff, cen, bb.ss, 1);
for(map<ll, int> :: iterator it = road.begin() ; it != road.end(); ++it)
if(final.find(K-(it->ff)) != final.end()) tmpans = min(tmpans, final[K - (it->ff)] + it->ss);
for(map<ll, int> :: iterator it = road.begin() ; it != road.end(); ++it)
if(final.find((it->ff)) != final.end()) final[(it->ff)] = min(final[(it->ff)], it->ss);else final[(it->ff)] = it->ss;
}
// cout<<"here we have \n";
// if(cen == 17 or cen == 13)
// for(map<ll, int> :: iterator it = final.begin() ; it != final.end(); ++it)
// cout<<"final["<<(it->ff)<<"] = "<<(it->ss)<<'\n';
ans = min(ans, tmpans);
// if(tmpans != inf)
// cerr<<"found tmpans = "<<tmpans<<" when cen = "<<cen<<'\n';
for(pll bb : g[cen])
if(!centroid_marked[bb.ff])
dcmp(bb.ff);
// cout<<"tmpans = "<<tmpans<<'\n';
}
int best_path(int NN,int KK,int H[][2],int L[])
{
K = KK;
F0R(i, NN)
centroid_marked[i] = false;
F0R(i, NN-1)
g[H[i][1]].pb(mp(H[i][0], L[i])), g[H[i][0]].pb(mp(H[i][1], L[i]));
ans = inf;
dcmp(0);
return (ans == inf) ? -1 : ans;
}
// signed main()
// {
// /*
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
// */
// int N, KK;
// cin>>N>>KK;
// int H[N-1][2], L[N-1];
// F0R(i, N-1)
// cin>>H[i][0]>>H[i][1]>>L[i];
// cout<<best_path(N, KK, H, L);
// return 0;
// }
/*
4 3
0 1 1
1 2 2
1 3 4
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/
