#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 =20; 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]; ll dp[20][(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; } ll calc(ll u,ll mask) { //if(__builtin_popcount(mask)==1) return val[u]; if(dp[u][mask]!=-1) return dp[u][mask]; ll nw=mask-(1<<u); if((nw&a[tin[u]])!=a[tin[u]]||(nw&a[tout[u]])!=a[tout[u]]) return dp[u][mask]=inf; dp[u][mask]=inf; /// i=m if(nw==0) { if(a[tin[u]]==0&&a[tout[u]]==0) dp[u][mask]=d[m][u]; return dp[u][mask]; } for(ll i=0;i<m;i++) if(bit(i,nw)) dp[u][mask]=min(dp[u][mask],calc(i,nw)+d[i][u]); //cout<<u<<" "<<mask<<" "<<tin[u]<<" "<<tout[u]<<' '<<" "<<dp[u][mask]<<'\n'; return dp[u][mask]; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin>>n>>s>>t; 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); if(a[t]==0) return cout<<dist(s,t),0; tin[m]=tout[m]=s; 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]=dist(tout[i],t); } memset(dp,-1,sizeof(dp)); ll res=inf; for(ll mask=0;mask<(1<<(m));mask++) if((mask&a[t])==a[t]){ for(ll i=0;i<m;i++) if(bit(i,mask)) res=min(res,calc(i,mask)+d[i][i]); } cout<<(res==inf?-1:res); return 0; } /* (2^d-1)*(2^k) / (2^n-1) 2^d+k-n - 2^k-n */