// Bismillahir Rahmanir Rahim //
// After hardship comes ease //
// AUTHOR : iamarman //
// pragmas
// #pragma GCC optimize("O3" )
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC optimize("tree-vectorize")
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
//// TEMPLATE ////
//---------------------------------------------------------------------------------------------------------------------------------|
# define el '\n'
# define sp " "
# define ff first
# define ss second
# define ll long long
# define pb push_back
# define mp make_pair
# define yess1 cout<<1<<el
# define noo cout<<"NO"<<el
# define yess cout<<"YES"<<el
# define siz(x) (int)x.size()
# define ull unsigned long long
# define all(v) v.begin(),v.end()
# define allr(v) v.rbegin(),v.rend()
# define torad(x) ((x) * ((2*acos(0))/180.0))
# define todeg(x) ((x) * (180.0/(2*acos(0))))
constexpr ll mod=998244353;
constexpr ll INF=2e18;
constexpr double PI= acos(-1);
constexpr double eps=1e-9;
# define mem(a,b) memset(a,b,sizeof(a))
# define sqr(a) ((a)*(a))
# define lcm(a,b) (a*b)/__gcd(a,b)
# define optimise { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
# define fraction(a) cout.unsetf(ios::floatfield); cout.precision(a); cout.setf(ios::fixed,ios::floatfield);
# define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// find_by_order() - Returns an iterator to the k-th largest element (counting from zero)
// order_of_key() - The number of items in a set that are strictly smaller than our item
// greater instead of less for descending order
// less_equal works as ordered multiset
// we can use pair<int,int> instead of int for pair of orderd set
// for multiset st.lower_bound(x) works as upper bound and st.upper_bound(x) works as lower bound
inline void file() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
//----------------------------------------------------------------------------------------------------------------------------------|
// DEBUGGER //
//----------------------------------------------------------------------------------------------------------------------------------|
template < typename F, typename S > ostream& operator << ( ostream& os, const pair< F, S > & p ) { return os << "(" << p.first << ", " << p.second << ")"; }
template < typename T > ostream &operator << ( ostream & os, const vector< T > &v ) { os << "{"; for(auto it = v.begin(); it != v.end(); ++it) { if( it != v.begin() ) os << ", "; os << *it; } return os << "}"; }
template < typename T > ostream &operator << ( ostream & os, const set< T > &v ) { os << "["; for(auto it = v.begin(); it != v.end(); ++it) { if( it != v.begin() ) os << ", "; os << *it; } return os << "]"; }
template < typename T > ostream &operator << ( ostream & os, const multiset< T > &v ) { os << "["; for(auto it = v.begin(); it != v.end(); ++it) { if( it != v.begin() ) os << ", "; os << *it; } return os << "]"; }
template < typename F, typename S > ostream &operator << ( ostream & os, const map< F, S > &v ) { os << "["; for(auto it = v.begin(); it != v.end(); ++it) { if( it != v.begin() ) os << ", "; os << it -> first << " = " << it -> second ; } return os << "]"; }
#define dbg(args...) do {cerr << #args << " : "; iamarman(args); } while(0)
void iamarman () { cerr << endl; }
template <typename T> void iamarman( T a[], int n ) { for(int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; }
template <typename T, typename ... hello> void iamarman( T arg, const hello &... rest) { cerr << arg << ' '; iamarman(rest...); }
//--------------------------------------------------------------------------------------------------------------------------------------|
///// FUNCTIONS /////
ll bigmod(ll base,ll power){ ll res=1; ll p=base%mod; while(power>0) { if(power%2==1) { res=((res%mod)*(p%mod))%mod; } power/=2; p=((p%mod)*(p%mod))%mod; } return res; }
ll inversemod(ll base) { return bigmod(base,mod-2); }
ll poww(ull a,ull b) { ull ans=1; if(!b) return 1; while(b>1) { if(b&1) { ans=ans*a%mod; } a=a*a%mod; b/=2; }return a*ans%mod; }
ll gcd(ll a,ll b) { ll rem; while(b%a!=0) { rem=b%a; b=a; a=rem; } return a; }
ll sqrtt(ll a){ long long x = sqrt(a) + 2; while (x * x > a) x--; return x;}
ll sqrt(ll n) {ll low=0,high=1e10; while(high-low>1){ ll mid=low+(high-low)/2; if(mid*mid<=n) low=mid; else high=mid; }return low; }
long double sqrtd(long double n){ long double low=0,high=n,mid; for(int i=0;i<100;i++) { mid=(low+high)/2; if(mid*mid<=n) low=mid; else high=mid;} return low;}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
inline ll getrandom(ll a,ll b) { return uniform_int_distribution<ll>(a,b)(rng); }
int dx[]={-1, 1 , 0 , 0 , -1 ,-1, 1, 1};
int dy[]={ 0, 0 ,-1 , 1 , -1 , 1,-1, 1};
// up = { -1,0 } , down = { 1,0 } , right = { 0,1 } , left = { 0,-1 }
// up-right = { -1,1 } , up-left = { -1,-1 } , down-right = { 1,1 } , down-left = { 1,-1 }
/// ____________CODE STARTS FROM HERE____________ ///
ll best_path(int N, int K, int H[][2], int L[])
{
int n=N,k=K;
vector<vector<pair<int,int>> > graph(n+1);
for(int i=1;i<=n;i++)
{
int u=H[i-1][0],v=H[i-1][1];
u++,v++;
int w=L[i-1];
graph[u].push_back({v,w});
graph[v].push_back({u,w});
}
vector<int> sz(n+1,0),used(n+1,0);
auto get_size=[&](auto &&self,int node,int par)->int
{
sz[node]=1;
for(auto it : graph[node])
{
if(it.ff==par or used[it.ff]) continue;
sz[node]+=self(self,it.ff,node);
}
return sz[node];
};
auto centroid=[&](auto &&self,int node,int par,int size)->int
{
for(auto it : graph[node])
{
if(it.ff==par or used[it.ff]) continue;
if(sz[it.ff]>size/2) return self(self,it.ff,node,size);
}
return node;
};
ll ans=INF;
vector<ll> mn(k+5,INF);
auto process=[&](int cent)->void
{
vector<int> nodes;
nodes.pb(0);
mn[0]=0;
for(auto [it,w] : graph[cent])
{
if(used[it]) continue;
vector<pair<ll,ll>> sub_dis;
auto get_dis=[&](auto &&self,int node,int par,int dis,ll cur)->void
{
if(cur>k) return;
sub_dis.pb({cur,dis});
for(auto [it,w] : graph[node])
{
if(it==par or used[it]) continue;
self(self,it,node,dis+1,cur+w);
}
};
get_dis(get_dis,it,cent,1,w);
for(auto d : sub_dis)
{
if(mn[k-d.ff]!=INF)
{
ans=min(ans, mn[k-d.ff]+d.ss);
}
}
for(auto it : sub_dis)
{
mn[it.ff]=min(mn[it.ff],it.ss);
}
for(auto d : sub_dis)
{
nodes.pb(d.ff);
}
}
for(auto d : nodes)
{
mn[d]=INF;
}
};
auto decompose=[&](auto &&self,int node,int cur)->void
{
int size=get_size(get_size,node,0);
int cent=centroid(centroid,node,0,size);
used[cent]=1;
process(cent);
for(auto [it,w] : graph[cent])
{
if(used[it]) continue;
self(self,it,cur+1);
}
};
decompose(decompose,1,0);
if(ans==INF) return -1;
return ans;
}
// void solve()
// {
// int n,k;
// cin>>n>>k;
// vector<vector<pair<int,int>> > graph(n+1);
// for(int i=1;i<n;i++)
// {
// int u,v,w;
// cin>>u>>v>>w;
// graph[u].push_back({v,w});
// graph[v].push_back({u,w});
// }
// vector<int> sz(n+1,0),used(n+1,0);
// auto get_size=[&](auto &&self,int node,int par)->int
// {
// sz[node]=1;
// for(auto it : graph[node])
// {
// if(it.ff==par or used[it.ff]) continue;
// sz[node]+=self(self,it.ff,node);
// }
// return sz[node];
// };
// auto centroid=[&](auto &&self,int node,int par,int size)->int
// {
// for(auto it : graph[node])
// {
// if(it.ff==par or used[it.ff]) continue;
// if(sz[it.ff]>size/2) return self(self,it.ff,node,size);
// }
// return node;
// };
// ll ans=INF;
// vector<ll> mn(k+5,INF);
// auto process=[&](int cent)->void
// {
// vector<int> nodes;
// nodes.pb(0);
// mn[0]=0;
// for(auto [it,w] : graph[cent])
// {
// if(used[it]) continue;
// vector<pair<ll,ll>> sub_dis;
// auto get_dis=[&](auto &&self,int node,int par,int dis,ll cur)->void
// {
// if(cur>k) return;
// sub_dis.pb({cur,dis});
// for(auto [it,w] : graph[node])
// {
// if(it==par or used[it]) continue;
// self(self,it,node,dis+1,cur+w);
// }
// };
// get_dis(get_dis,it,cent,1,w);
// for(auto d : sub_dis)
// {
// if(mn[k-d.ff]!=INF)
// {
// ans=min(ans, mn[k-d.ff]+d.ss);
// }
// }
// for(auto it : sub_dis)
// {
// mn[it.ff]=min(mn[it.ff],it.ss);
// }
// for(auto d : sub_dis)
// {
// nodes.pb(d.ff);
// }
// }
// for(auto d : nodes)
// {
// mn[d]=INF;
// }
// };
// auto decompose=[&](auto &&self,int node,int cur)->void
// {
// int size=get_size(get_size,node,0);
// int cent=centroid(centroid,node,0,size);
// used[cent]=1;
// process(cent);
// for(auto [it,w] : graph[cent])
// {
// if(used[it]) continue;
// self(self,it,cur+1);
// }
// };
// decompose(decompose,1,0);
// cout<<ans<<el;
// }
// int main()
// {
// optimise;
// file();
// clock_t start= clock();
// int t=1;
// //cin>>t;
// for(int i=1;i<=t;i++)
// {
// solve();
// }
// cerr << "Run Time : " <<((double)(clock() - start) / CLOCKS_PER_SEC)<<el;
// }
