Cho một mạng có ~N~ đỉnh, ~M~ cạnh vô hướng và một đỉnh phát ~S~. Mỗi cạnh ~(X~, ~Y)~ của mạng có khả năng thông qua là ~K~. Hãy tìm cách chọn ~1~ đỉnh thu ~T~ khác với ~S~ sao cho luồng cực đại trên mạng với đỉnh phát ~S~ và đỉnh thu ~T~ có giá trị nhỏ nhất.

Input

Có nhiều bộ test, dữ liệu kết thúc bằng "0 ~0~ 0". Với mỗi test:

• Dòng đầu chứa ~3~ số nguyên ~N~, ~M~ và ~S~, thể hiện số đỉnh, số cạnh, và chỉ số đỉnh phát (các đỉnh đánh số từ ~1~ đến ~N)~.(~1 < N \leq 300~, ~0 < M \leq 50000~, ~0 < S \leq N~ )
• ~M~ dòng tiếp theo mô tả các cạnh của đồ thị. Mỗi dòng chứa ~3~ số nguyên ~X~, ~Y~ và ~K~, thể hiện một cạnh nối ~2~ đỉnh ~X~ và ~Y~ với khả năng thông qua là ~K~. (~0 < X~, ~Y \leq N~, ~0 < K \leq 1000000~ )

Output

• Với mỗi test, in ra ~1~ số nguyên ~W~ duy nhất thể hiện luồng cực đại nhỏ nhất tìm được trong số các cách chọn đỉnh thu.

Sample Input

5 5 1
1 2 5
2 4 6
1 3 7
3 4 3
5 1 10
0 0 0

Sample Output

8