#include <bits/stdc++.h> #define ll int #define fi first #define se second #define pb push_back #define ii pair<ll, ll> #define all(a) a.begin(), a.end() #define iii pair<ll, ii> #define ld long double using namespace std; #pragma GCC optimize("Ofast,O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") const ll N = 1e6+5; const ll mod = 1e9+7; const ll inf=1e9+3; const ll lg =18; ll n,i,j,m=0,q,k; ll x,y; ll s,t,cnt=0; ll d[23][23],tin[23],tout[23]; ll up[20][N],a[N],par[N],deep[N]; vector<ii>v[N]; bool kt[22][(1<<20)]; bool bit(ll i,ll x) { return (x>>i)&1; } ll binlift(ll x,ll k) { for(ll i=0;i<20;i++) if((k>>i)&1) x=up[i][x]; return x; } ll LCA(ll x,ll y) { if(deep[x]<deep[y]) swap(x,y); x=binlift(x,deep[x]-deep[y]); if(x==y) return x; for(ll i=19;i>=0;i--) { if(up[i][x]!=up[i][y]) { x=up[i][x]; y=up[i][y]; } } return up[0][x]; } void dfs(ll u,ll p) { up[0][u]=p; for(ll i=1;i<20;i++) up[i][u]=up[i-1][up[i-1][u]]; deep[u]=deep[p]+1; par[u]=p; for(auto tmp:v[u]) { ll x=tmp.fi,w=tmp.se; if(x==p) continue; a[x]=a[u]; if(w!=0) { tin[m]=w; tout[m]=u; a[x]|=(1<<m); m++; } dfs(x,u); } } ll dist(ll x,ll y) { ll lca=LCA(x,y); //cout<<x<<" "<<y<<' '<<deep[x]+deep[y]-deep[lca]*2<<'\n'; return deep[x]+deep[y]-deep[lca]*2; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin>>n>>s>>t; if(s==t) return cout<<0,0; for(i=1;i<n;i++) { ll x,y,w; cin>>x>>y>>w; v[x].pb({y,w}); v[y].pb({x,w}); } memset(a,0,sizeof(a)); dfs(s,s); tin[m]=tout[m]=s; ++m; tin[m]=tout[m]=t; for(i=0;i<=m;i++){ for(j=0;j<=m;j++) if(j!=i) { d[i][j]=dist(tout[i],tin[j])+dist(tin[j],tout[j]); } d[i][i]=0; } priority_queue<iii,vector<iii>,greater<iii>>pq;// dis mask cur pq.push({0ll,{0ll,m-1}}); ll res=inf; while(!pq.empty()) { iii tmp=pq.top();pq.pop(); ll dis=tmp.fi,mask=tmp.se.fi,u=tmp.se.se; // cout<<u<<" "<<dis<<" "<<mask<<'\n'; if(res<=dis) break; if(kt[u][mask]) continue; kt[u][mask]=1; for(ll i=0;i<m-1;i++) if(!bit(i,mask)&&(a[tin[i]]&mask)==a[tin[i]]&&(a[tout[i]]&mask)==a[tout[i]]&&!kt[i][mask|(1<<i)]) pq.push({dis+d[u][i],{mask|(1<<i),i}}); if((a[t]&mask)==a[t]) res=min(res,dis+d[u][m]); } cout<<(res==inf?-1:res); return 0; } /* (2^d-1)*(2^k) / (2^n-1) 2^d+k-n - 2^k-n */