#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#include "race.h"
#define a first
#define pb push_back
#define b second
pair<int,int> aa[1000001];
pair<int,int> bb[1000001];
int ss[200001];
set<pair<int,int>> adj[200001];
int cur;
vector<int> del;
int k;
int ans=-1;
void dfs(int no,int par=-1){
ss[no]=1;
for(auto j:adj[no]){
if(j.a!=par){
dfs(j.a,no);
ss[no]+=ss[j.a];
}
}
}
int dfs2(int no,int par=-1){
for(auto j:adj[no]){
if(j.a==par){
continue;
}
if(ss[j.a]>ss[cur]/2){
return dfs2(j.a,no);
}
}
return no;
}
void dfs3(int no,int par2,int par=-1,int lev=0,int ww=0){
if(lev==1){
par2=no;
}
if(ww<=k){
del.pb(ww);
if(aa[ww].a==-1){
aa[ww]={par2,lev};
}
else if(aa[ww].a==par2){
aa[ww].b=min(aa[ww].b,lev);
}
else if(aa[ww].b>lev){
bb[ww]=aa[ww];
aa[ww]={par2,lev};
}
else if(bb[ww].a==-1){
bb[ww]={par2,lev};
}
else if(bb[ww].a==par2){
bb[ww].b=min(bb[ww].b,lev);
}
else if(lev<bb[ww].b){
bb[ww]={par2,lev};
}
if(aa[ww].a!=-1 and aa[k-ww].a!=-1){
if(aa[ww].a!=aa[k-ww].a){
if(ans==-1){
ans=aa[ww].b+aa[k-ww].b;
}
ans=min(ans,aa[ww].b+aa[k-ww].b);
}
}
if(aa[ww].a!=-1 and bb[k-ww].a!=-1){
if(aa[ww].a!=bb[k-ww].a){
if(ans==-1){
ans=aa[ww].b+bb[k-ww].b;
}
ans=min(ans,aa[ww].b+bb[k-ww].b);
}
}
if(bb[ww].a!=-1 and aa[k-ww].a!=-1){
if(bb[ww].a!=aa[k-ww].a){
if(ans==-1){
ans=bb[ww].b+aa[k-ww].b;
}
ans=min(ans,bb[ww].b+aa[k-ww].b);
}
}
if(bb[ww].a!=-1 and bb[k-ww].a!=-1){
if(bb[ww].a!=bb[k-ww].a){
if(ans==-1){
ans=bb[ww].b+bb[k-ww].b;
}
ans=min(ans,bb[ww].b+bb[k-ww].b);
}
}
}
for(auto j:adj[no]){
if(j.a==par){
continue;
}
dfs3(j.a,par2,no,lev+1,ww+j.b);
}
}
void dec(int no){
cur=no;
dfs(no);
//return;
int cen=dfs2(no);
dfs3(cen,cen);
for(auto j:del){
aa[j]={-1,-1};
bb[j]={-1,-1};
}
del.clear();
for(auto j:adj[cen]){
adj[j.a].erase({cen,j.b});
}
for(auto j:adj[cen]){
dec(j.a);
}
return;
}
int best_path(int n,int kk,int h[][2],int l[]){
k=kk;
for(int i=0;i<=k;i++){
aa[i]={-1,-1};
bb[i]={-1,-1};
}
for(int i=0;i<n-1;i++){
adj[h[i][0]].insert({h[i][1],l[i]});
adj[h[i][1]].insert({h[i][0],l[i]});
}
dec(0);
return ans;
}
/*int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,ko;
cin>>n>>ko;
int hh[n-1][2];
int lol[n-1];
for(int i=0;i<n-1;i++){
cin>>hh[i][0]>>hh[i][1]>>lol[i];
}
cout<<best_path(n,ko,hh,lol)<<endl;
return 0;
}
*/
