1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define pii pair<int, int>
19 #define mp make_pair
20 #define maxn 10050
21 #define maxm 1000050
22 
23 int n, s, cnt;
24 int eh[maxn], tot;
25 int dp[maxn][15];
26 struct Edge {
27     int u, v, w, next;
28 }et[maxm];
29 
30 void addedge(int u, int v, int w) {
31     Edge e = {u, v, w, eh[u]};
32     et[tot] = e;
33     eh[u] = tot++;
34 }
35 
36 void init() {
37     tot = 0;
38     memset(eh, -1, sizeof(eh));
39 }
40 
41 void dfs(int u, int fa) {
42     for(int i = eh[u]; i != -1; i = et[i].next) {
43         int v = et[i].v, w = et[i].w;
44         if(v == fa) continue;
45         dfs(v, u);
46         for(int j = cnt; j >= 0; j--) {
47             dp[u][j] += dp[v][0] + 2 * w;
48             for(int k = 1; k <= j; k++) {
49                 dp[u][j] = min(dp[u][j], dp[u][j-k] + dp[v][k] + k * w);
50             }
51         }
52     }
53 }
54 
55 int main() {
56     int u, v, w;
57     while(~scanf("%d%d%d", &n, &s, &cnt)) {
58         init();
59         memset(dp, 0, sizeof(dp));
60         for(int i = 0; i < n - 1; i++) {
61             scanf("%d%d%d", &u, &v, &w);
62             addedge(u, v, w), addedge(v, u, w);
63         }
64         dfs(s, -1);
65         printf("%d\n", dp[s][cnt]);
66     }
67     return 0;
68 }
69