#include <bits/stdc++.h>
using namespace std;
#define NMAX 200010
#define KMAX 1000010
#define LOGMAX 17
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair< ll, ll > pll;
typedef pair< pll, ll > pplll;
typedef vector< ll > vl;
typedef vector< pll > vpll;
ll n, m;
vpll grafo[NMAX];
ll level[NMAX];
ll anc[NMAX][LOGMAX + 1];
ll dist[NMAX][LOGMAX + 1];
ll qtdCent;
ll pai[NMAX];
ll sub[NMAX];
stack< ll > ordem;
ll caso = 1;
ll marc[KMAX];
pll best[KMAX];
pll best2[KMAX];
vpll children[NMAX];
vpll paths;
void DFS(ll u, ll p, ll d)
{
level[u] = level[p] + 1;
anc[u][0] = p;
dist[u][0] = d;
for(ll i = 1;i <= LOGMAX;i++)
{
anc[u][i] = anc[ anc[u][i - 1] ][i - 1];
dist[u][i] = dist[u][i - 1] + dist[ anc[u][i - 1] ][i - 1];
}
for(auto viz : grafo[u])
{
ll w = viz.fi;
ll v = viz.se;
if(v == p) continue;
DFS(v, u, w);
}
return;
}
pll Dist(ll u, ll v)
{
ll i, d = 0LL, qtd = 0LL;
if(level[u] < level[v]) swap(u, v);
for(i = LOGMAX;i >= 0;i--)
{
if(level[u] - (1 << i) >= level[v])
{
qtd += (1 << i);
d += dist[u][i];
u = anc[u][i];
}
}
if(u == v) return {d, qtd};
for(i = LOGMAX;i >= 0;i--)
{
if(anc[u][i] != anc[v][i])
{
qtd += (1 << i);
d += dist[u][i];
qtd += (1 << i);
d += dist[v][i];
u = anc[u][i];
v = anc[v][i];
}
}
i = 0;
qtd += (1 << i);
d += dist[u][i];
qtd += (1 << i);
d += dist[v][i];
return {d, qtd};
}
ll DFSCentroid(ll u, ll p)
{
sub[u] = 1;
for(auto viz : grafo[u])
{
ll v = viz.se;
if(v == p || pai[v] != 0) continue;
sub[u] += DFSCentroid(v, u);
}
return sub[u];
}
ll FindCentroid(ll u, ll p)
{
for(auto viz : grafo[u])
{
ll v = viz.se;
if(v == p || pai[v] != 0) continue;
if(2 * sub[v] > qtdCent) return FindCentroid(v, u);
}
return u;
}
void BuildCentroid(ll u, ll p)
{
qtdCent = DFSCentroid(u, u);
ll centroid = FindCentroid(u, u);
pai[centroid] = p;
ordem.push(centroid);
for(auto viz : grafo[centroid])
{
ll v = viz.se;
if(pai[v] == 0) BuildCentroid(v, centroid);
}
return;
}
ll Query(pll path, ll who)
{
ll d = path.fi;
ll q = path.se;
if(0 <= m - d && marc[m - d] == caso)
{
if(who != best[m - d].se) return best[m - d].fi + q;
else return best2[m - d].fi + q;
}
return NMAX;
}
int best_path (int auxN, int auxM, int h[][2], int l[])
{
ll tam, u, v, w, d, q, pos, resp, i, j, k;
n = auxN;
m = auxM;
pll path;
resp = NMAX;
for(i = 0;i < n - 1;i++)
{
u = h[i][0];
v = h[i][1];
w = l[i];
u++;
v++;
grafo[u].pb({w, v});
grafo[v].pb({w, u});
}
DFS(1, 1, 0);
BuildCentroid(1, -1);
for(i = 1;i <= n;i++) children[i].pb({i, i});
while(ordem.empty() == false)
{
u = ordem.top();
ordem.pop();
tam = children[u].size();
paths.clear();
for(auto ch : children[u]) paths.pb(Dist(u, ch.fi));
for(i = 0;i < tam;i++)
{
d = paths[i].fi;
q = paths[i].se;
if(m < d) continue;
marc[d] = caso;
best[d] = {NMAX, -1};
best2[d] = {NMAX, -1};
}
for(i = 0;i < tam;i++)
{
d = paths[i].fi;
q = paths[i].se;
if(m < d) continue;
best[d] = min(best[d], {q, children[u][i].se});
}
for(i = 0;i < tam;i++)
{
d = paths[i].fi;
q = paths[i].se;
if(m < d || children[u][i].se == best[d].se) continue;
best2[d] = min(best2[d], {q, children[u][i].se});
}
pos = 0;
i = 0;
while(i < tam)
{
j = i;
while(j < tam && children[u][i].se == children[u][j].se)
j++;
v = children[u][i].se;
for(k = i;k < j;k++)
resp = min(resp, Query(paths[k], v));
i = j;
}
v = pai[u];
if(v != -1)
{
for(auto ch : children[u]) children[v].pb({ch.fi, u});
}
children[u].clear();
caso++;
}
if(resp == NMAX) resp = -1;
return resp;
}
