#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> // #ifndef ONLINE_JUDGE // #include "00_debug.h" // #else // #define debug(x) // #endif #define endl '\n' #define all(a) a.begin(), a.end() typedef long long ll; using namespace std; using namespace __gnu_pbds; template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; void solve(){ int n,k,x; cin>>n>>k>>x; vector<vector<pair<int,int>>>g(n); for(int i=1;i<n;i++){ int u,v,w; cin>>u>>v>>w; u--,v--; g[u].push_back({v,w}); g[v].push_back({u,w}); } vector<vector<vector<ll>>>dp(n); vector<int>sz(n); vector<int>mx(n); function<void(int,int)>dfs1=[&](int node,int parent){ mx[node]=1; for(auto child:g[node]){ if(child.first==parent)continue; dfs1(child.first,node); mx[node]+=mx[child.first]; } }; x--; dfs1(x,-1); function<void(int,int)>dfs=[&](int node,int parent){ dp[node]=vector<vector<ll>>(mx[node]+1,vector<ll>(2,1e18)); dp[node][1][0]=dp[node][1][1]=0; sz[node]=1; for(auto child:g[node]){ if(child.first==parent)continue; dfs(child.first,node); auto ndp=dp[node]; for(int i=1;i<=sz[node];i++){ if(dp[node][i][1]==1e18)continue; for(int j=1;j<=sz[child.first];j++){ if(dp[child.first][j][0]!=1e18)ndp[i+j][0]=min(ndp[i+j][0],dp[node][i][1]+dp[child.first][j][0]+child.second); if(dp[child.first][j][1]!=1e18){ ndp[i+j][1]=min(ndp[i+j][1],dp[node][i][1]+dp[child.first][j][1]+2*child.second); ndp[i+j][0]=min(ndp[i+j][0],dp[node][i][1]+dp[child.first][j][1]+child.second); } } } sz[node]+=sz[child.first]; swap(ndp,dp[node]); } }; dfs(x,-1); cout<<min(dp[x][k][0],dp[x][k][1])<<endl; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // #ifndef ONLINE_JUDGE // freopen("Input.txt","r",stdin); // freopen("output.txt","w",stdout); // freopen("Error.txt","w",stderr); // #endif int t=1; // cin >> t; while(t--){ solve(); } return 0; }