Drainage Ditches

Drainage Ditches Hal Burch Trời lúc nào cũng mưa trên những cánh đồng của ông chủ trại John. Khoảng giữa của bãi cỏ bị ngập nước như một cái ao trong một thời gian và rút đi rất chậm. Vì thế nên ông John đã xây dựng một mạng lưới các mương thoát nước sao cho bãi cỏ không bao giờ bị ngập nước. Khi đó, nước sẽ chảy ra con suối bên cạnh . Là một kỹ sư giỏi, ông John cũng đã lắp đặt được hệ thống các máy điều khiển ở đầu mỗi con mương nên kiểm soát được tốc độ (lưu lượng) của các luồng nước chảy vào bên trong mỗi con mương. Ông John không những biết bao nhiêu gallons (đơn vị thể tích) nước mỗi con mương chảy qua trong một phút mà còn biết chính xác trạng thái của những con mương chảy ra từ cái ao sang các con mương khác và chảy ra suối trong toàn bộ mạng lưới . Cho biết tất cả các thông tin này, hãy tìm tốc độ cực đại cuả các dòng nước từ cái ao chảy ra suối. Đối với mỗi con mương dòng nước chỉ chảy theo một chiều nhưng đường đi của các dòng nước có thể là một đường vòng(circle).

PROGRAM NAME: ditch INPUT FORMAT Dòng 1:

Dòng 2..N+1:

Cho hai số nguyên N (0 <= N <= 200) và M (2 <= M <= 200). N là số lượng các con mương mà ông John đã đào. M là số lương các điểm giao nhau cuả các con mương này. Điểm giao nhau số 1 là cái ao. Điểm M là con suối. Mỗi dòng chứa 3 số nguyên Si, Ei,và Ci. Si và Ei (1 <= Si, Ei <= M) là chỉ số cuả các điểm ở hai đầu con mương . Nước sẽ chảy theo con mương từ Si đến Ei. Ci (0 <= Ci <= 10,000,000) là tốc độ lớn nhất mà nước có thể chảy qua mương.

SAMPLE INPUT (file ditch.in) 5 1 1 2 2 3

4 2 4 4 3 4

40 20 20 30 10

OUTPUT FORMAT Ghi Một số nguyên V là tốc độ cực đại của nước chảy ra từ cái ao. SAMPLE OUTPUT (file ditch.out) 50

Submission file Name: Submit Solution via Email | USACO Gateway | Comment or Question