#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define vi vector<int> #define pb push_back #define all(a) a.begin(),a.end() const int mxn = 10001, inf = 1e9; vector<pii> g[mxn]; vector<int> dp[mxn], dp2[mxn]; int sub[mxn]; int n,k,r; void dfs(int u, int p){ sub[u] = 1; dp[u].resize(2,0); dp2[u].resize(2,0); for(auto [v,c] : g[u]) if(v!=p){ dfs(v,u); dp[u].resize(min(sub[u]+sub[v]+1,k+1),inf); dp2[u].resize(min(sub[u]+sub[v]+1,k+1),inf); for(int i = min(sub[u]+sub[v],k); i; i--) for(int j = max(1,i-sub[v]); j <= min(i,sub[u]); j++){ dp[u][i] = min(dp[u][i],dp[u][j] + dp[v][i-j] + 2*c); dp2[u][i] = min(dp2[u][i],dp[u][j] + dp2[v][i-j] + c); dp2[u][i] = min(dp2[u][i],dp2[u][j] + dp[v][i-j] + 2*c); } sub[u] += sub[v]; } } void solve(){ cin >> n >> k >> r; for(int i = 1; i < n; i++){ int u,v,c; cin >> u >> v >> c; g[u].pb({v,c}); g[v].pb({u,c}); } dfs(r,r); cout << dp2[r][k]; } signed main(){ cin.tie(0)->sync_with_stdio(0); int t = 1; // cin >> t; while(t--){solve();} }