#include<iostream> #include<algorithm> #include<vector> using namespace std; #define ll long long #define ld long double #define pii pair<int, int> #define pli pair<ll, ll> #define RUN_LIKE_DJAWAD (ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)); #define DECIMAL_OUTPUT cout << fixed << setprecision(9); #define pb push_back #define pf push_top #define ff first #define ss second #define maxn 10001 #define inf 200000000 vector<pii> g[maxn]; int E1[maxn], E2[maxn], H1[maxn], H2[maxn]; bool seen[maxn]; int dfs(int v, int pt){ seen[v] = true; E1[pt] = 0, E2[pt] = 0; int SZN = 1; for (auto [u, w]: g[v]) if (not seen[u]){ int szc = dfs(u, pt + SZN); for (int i = 0; i < SZN; i++) H1[i] = E1[pt + i], H2[i] = E2[pt + i]; for (int i = 0; i < szc; i++) H1[SZN + i] = inf, H2[SZN + i] = inf; for (int i = 0; i < SZN; i++) for (int j = 0; j < szc; j++){ H1[i + j + 1] = min({H1[i + j + 1], E1[pt + i] + E2[pt + SZN + j] + (w << 1), E2[pt + i] + E1[pt + SZN + j] + w}); H2[i + j + 1] = min(H2[i + j + 1], E2[pt + i] + E2[pt + SZN + j] + (w << 1)); } SZN += szc; for (int i = 0; i < SZN; i++) E1[pt + i] = H1[i], E2[pt + i] = H2[i]; } return SZN; } int n, k, s, ui, vi, ci; int main(){ RUN_LIKE_DJAWAD cin >> n >> k >> s; for (int i = 1; i < n; i++){ cin >> ui >> vi >> ci; g[ui].pb({vi, ci}); g[vi].pb({ui, ci}); } dfs(s, 0); cout << E1[k - 1] << "\n"; }