#include <bits/stdc++.h> using namespace std; int n, k, X; vector<vector<int>> dp1[2]; vector<int> num; vector<vector<pair<int, int>>> adj; void solve2(int x, int p) { vector<vector<int>> dp2[2]; for (auto v: adj[x]) { if (v.first == p) continue; solve2(v.first, x); } dp1[0][x].push_back(0); dp1[1][x].push_back(0); dp2[0].push_back({}); dp2[1].push_back({}); dp2[0][0].push_back(0); dp2[1][0].push_back(0); int s = 0; int cnt = 0; for (auto v: adj[x]) { if (v.first == p) continue; dp2[0].push_back({}); dp2[1].push_back({}); for (int i = 0; i <= min(s + num[v.first], k - 1); i++) { for (int j = max(0, i - num[v.first]); j <= min({s, k - 1, i}); j++) { if (j == max(0, i - num[v.first])) { if (i != j) { dp2[0].back().push_back(min(dp2[0][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second, dp2[1][cnt][j] + dp1[0][v.first][i - j]) + v.second); dp2[1].back().push_back(dp2[1][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second); } else { dp2[0].back().push_back(dp2[0][cnt][j]); dp2[1].back().push_back(dp2[1][cnt][j]); } } else { if (i != j) { dp2[0][cnt + 1][i] = min(dp2[0][cnt + 1][i], min(dp2[0][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second, dp2[1][cnt][j] + dp1[0][v.first][i - j] + v.second)); dp2[1][cnt + 1][i] = min(dp2[1][cnt + 1][i], dp2[1][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second); } else { dp2[0][cnt + 1][i] = min(dp2[0][cnt + 1][i], dp2[0][cnt][j]); dp2[1][cnt + 1][i] = min(dp2[1][cnt + 1][i], dp2[1][cnt][j]); } } } } s += num[v.first]; cnt++; } for (int i = 0; i < (int)dp2[0][cnt].size(); i++) { dp1[0][x].push_back(dp2[0][cnt][i]); } for (int i = 0; i < (int)dp2[1][cnt].size(); i++) { dp1[1][x].push_back(dp2[1][cnt][i]); } } int solve() { vector<vector<int>> dp2[2]; for (auto v: adj[X]) { solve2(v.first, X); } dp2[0].push_back({}); dp2[1].push_back({}); dp2[0][0].push_back(0); dp2[1][0].push_back(0); int s = 0; int cnt = 0; for (auto v: adj[X]) { dp2[0].push_back({}); dp2[1].push_back({}); for (int i = 0; i <= min(s + num[v.first], k - 1); i++) { for (int j = max(0, i - num[v.first]); j <= min({s, k - 1, i}); j++) { if (j == max(0, i - num[v.first])) { if (i != j) { dp2[0].back().push_back(min(dp2[0][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second, dp2[1][cnt][j] + dp1[0][v.first][i - j]) + v.second); dp2[1].back().push_back(dp2[1][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second); } else { dp2[0].back().push_back(dp2[0][cnt][j]); dp2[1].back().push_back(dp2[1][cnt][j]); } } else { if (i != j) { dp2[0][cnt + 1][i] = min(dp2[0][cnt + 1][i], min(dp2[0][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second, dp2[1][cnt][j] + dp1[0][v.first][i - j] + v.second)); dp2[1][cnt + 1][i] = min(dp2[1][cnt + 1][i], dp2[1][cnt][j] + dp1[1][v.first][i - j] + 2 * v.second); } else { dp2[0][cnt + 1][i] = min(dp2[0][cnt + 1][i], dp2[0][cnt][j]); dp2[1][cnt + 1][i] = min(dp2[1][cnt + 1][i], dp2[1][cnt][j]); } } } } s += num[v.first]; cnt++; } return dp2[0][cnt][k - 1]; } void init(int x, int p = -1) { num[x] = 1; for (auto v: adj[x]) { if (v.first == p) continue; init(v.first, x); num[x] += num[v.first]; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> k >> X; adj.resize(n); dp1[0].resize(n); dp1[1].resize(n); num.resize(n); X--; for (int i = 0; i < n - 1; i++) { int a, b, c; cin >> a >> b >> c; a--; b--; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } init(X); cout << solve() << "\n"; }