#include<bits/stdc++.h>
using namespace std;
const int INF = (int) 1e9;
const int N = 100100;
vector< pair< int, int > > tree[N];
vector< int > g[N];
int n, k, ans;
namespace decomposition {
int cnt[N], depth[N], f[N];
map< int, int > mp;
vector< pair< int, int > > ve;
int dfs (int u, int p = -1) {
cnt[u] = 1;
for (int v : g[u])
if (!depth[v] && v != p)
cnt[u] += dfs(v, u);
return cnt[u];
}
int get_centroid (int u, int r, int p = -1) {
for (int v : g[u])
if (!depth[v] && v != p && cnt[v] > r)
return get_centroid(v, r, u);
return u;
}
void explore( int u, int p, int cost, int d )
{
if( cost > k ) return;
ve.push_back( { cost, d } );
for( auto e : tree[u] )
{
int v = e.first, w = e.second;
if( !depth[v] )
explore( v, u, cost + w, d + 1 );
}
}
void solve( int centroid )
{
mp.clear();
mp[0] = 0;
for( auto e : tree[centroid] )
{
int v = e.first, w = e.second;
if( !depth[v] )
{
ve.clear();
explore( v, centroid, w, 1 );
for( auto it : ve )
{
if( mp.count( k - it.first ) )
ans = min( ans, mp[k-it.first] + it.second );
}
for( auto it : ve )
mp[it.first] = min( mp[it.first], it.second );
}
}
}
int decompose (int u, int d = 1) {
int centroid = get_centroid(u, dfs(u) >> 1);
depth[centroid] = d;
solve( centroid );
/// add here magic function to count properties on paths
for (int v : g[centroid])
if (!depth[v])
f[decompose(v, d + 1)] = centroid;
return centroid;
}
int lca (int u, int v) {
for (; u != v; u = f[u])
if (depth[v] > depth[u])
swap(u, v);
return u;
}
}
int best_path( int nn, int kk, int h[][2], int l[] )
{
n = nn, k = kk, ans = INF;
for( int e = 0; e < n - 1; ++ e )
{
int u = h[e][0], v = h[e][1], w = l[e];
tree[u].push_back( { v, w } );
tree[v].push_back( { u, w } );
g[u].push_back( v );
g[v].push_back( u );
}
decomposition::decompose( 0 );
return ( ans == INF ? -1 : ans );
}
