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 mp make_pair
15 #define fi first
16 #define se second
17 #define lc(x) (x << 1)
18 #define rc(x) (x << 1 | 1)
19 #define lowbit(x) (x & (-x))
20 #define ll long long
21 #define maxn 510
22 const int inf = 1 << 27;
23 int maz[maxn][maxn];
24 int n, m, s;
25 int StoerWagner(int n) {
26     int cnt = n, s, t;
27     int cut = inf;
28     bool visit[maxn], use[maxn];
29     int dist[maxn];
30     memset(use, false, sizeof(use));
31     while(--cnt > 0) {
32         memset(visit, false, sizeof(visit));
33         memset(dist, 0, sizeof(dist));
34         int u = 0;
35         while(use[u]) u++;
36         visit[u] = true;
37         for(int v = 0; v < n; v++)
38             if(!use[v] && !visit[v])
39                 dist[v] = maz[v][u];
40         s = t = u;
41         for(int i = u; i < n; i++) {
42             int max = 0, idx = u;
43             for(int j = 0; j < n; j++)
44                 if(!use[j] && !visit[j] && dist[j] > max)
45                     max = dist[idx = j];
46             if(!max) break;
47             visit[idx] = true;
48             for(int j = 0; j < n; j++)
49                 if(!use[j] && !visit[j])
50                     dist[j] += maz[j][idx];
51             s = t, t = idx;
52         }
53         cut = min(cut, dist[t]);
54         use[t] = true;
55         for(int i = 0; i < n; i++)
56             if(!use[i]) {
57                 maz[s][i] += maz[t][i];
58                 maz[i][s] += maz[i][t];
59             }
60 
61     }
62     return cut;
63 }
64 
65 int main() {
66     while(~scanf("%d%d%d", &n, &m, &s)) {
67         if(!n) break;
68         memset(maz, 0, sizeof(maz));
69         for(int i = 0; i < m; i++) {
70             int a, b, c;
71             scanf("%d%d%d", &a, &b, &c);
72             a--, b--;
73             maz[a][b] += c;
74             maz[b][a] += c;
75         }
76         int ans = StoerWagner(n);
77         cout << ans << endl;
78     }
79     return 0;
80 }
81