FZ10B - Nubulsa Expo

Tóm tắt đề:

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 NM 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).

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 XY 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.

Giới hạn:

1 < N ≤ 300, 0 < M ≤ 50000, 0 < SXY ≤ N, 0 < K ≤ 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


Được gửi lên bởi:Race with time
Ngày:2012-08-24
Thời gian chạy:0.101s-0.108s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:ACM ICPC Fuzhou 2010

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.