#include <bits/stdc++.h> #define all(x) (x).begin(), (x).end() #define rall(x) x.rbegin(), x.rend() using namespace std; using ll = long long; constexpr long long inf = LLONG_MAX; constexpr int mod = 1000000007; template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { for (size_t i = 0; i < v.size(); ++i) { os << v[i]; if (i + 1 < v.size()) { os << " "; } } return os; } template<typename T> istream& operator>>(istream& is, vector<T>& v) { for (auto& x : v) { is >> x; } return is; } void solve(){ int n, k, x; cin>>n>>k>>x; vector<vector<pair<int, int>>> g(n+1); for (int i = 0; i<n-1; i++){ int u, v, c; cin>>u>>v>>c; g[u].push_back({v, c}); g[v].push_back({u, c}); } vector<vector<vector<ll>>> dp(n+1); vector<int> sz(n+1); auto dfs = [&] (auto&& self, int u, int p) -> void { sz[u] = 1; for (auto [e, w]: g[u]){ if (e!=p){ self(self, e, u); sz[u]+=sz[e]; } } dp[u].assign(sz[u]+1, vector<ll>(2, 1e18)); dp[u][1][0] = dp[u][1][1] = 0; int L = min(k, sz[u]); for (auto [e, w]: g[u]){ if (e!=p){ vector<vector<ll>> ndp = dp[u]; for (int i = 1; i<=L; i++){ for (int j = 1; j<=min(sz[e], L-i); j++){ ndp[i+j][0] = min(ndp[i+j][0], dp[e][j][0]+dp[u][i][1]+w); ndp[i+j][0] = min(ndp[i+j][0], dp[e][j][1]+dp[u][i][0]+2*w); ndp[i+j][1] = min(ndp[i+j][1], dp[e][j][1]+dp[u][i][1]+2*w); } } swap(dp[u], ndp); } } }; dfs(dfs, x, x); cout<<dp[x][k][0]; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; //cin>>t; while(t--){ solve(); cout<<endl; } }