Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BAOVE - Bảo vệ

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/baove


Một mạng lưới gồm N thành phố, và một số đường một chiều nối các cặp thành phố (giữa hai thành phố có thể có nhiều đường nối một chiều).
Quân địch đang tập trung ở thành phố N, định tiến công ta ở thành phố 1, và chúng sẽ tiến công trên tất cả các con đường chưa được bảo vệ để tiến vào thành phố 1. Bộ chỉ huy ta cần xác định số quân ít nhất trên các con đường để chặn địch tiến về thành phố 1.

Input

Dòng đầu ghi N (N ≤ 5000)
Các dòng tiếp theo cho đến hết file, mỗi dòng một tả 1 đường gồm u, v, s cho biết có đoạn đường một chiều từ u đến v, và phải cần ít nhất s quân để chặn địch trên đường này. (s ≤ 65000)
Có không quá 10000 đường.

Output

Số quân ít nhất cần điều động

Example

Input:
10
10 7 25050
6 1 12564
10 4 23916
5 1 61054
10 9 50950
9 1 35558
10 2 60941
3 1 22203
8 2 2853
5 7 31422
3 7 41491
8 7 27235
4 8 55965
8 6 41980
3 6 47707
2 3 45320
3 8 11237
7 6 38734
5 6 7561
3 5 8844

Output:
79169


Được gửi lên bởi:Nguyen Dinh Tu
Ngày:2006-11-17
Thời gian chạy:1s
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ừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2019-10-23 05:41:00
như ông ở dưới, bài này chỉ là tìm luồng cực đại
2019-06-14 13:58:43
Edmondkarp hoặc Dinic. Bài này chỉ là tìm luồng cực đại.
(Nakroth 10000 thông thạo)
2018-10-10 09:34:09
nhật hào sạch
2018-08-29 09:51:32
nhật hào sạch
2018-01-03 14:03:14
ledacthuongvq
2017-10-26 10:39:49
code AC
http://bfy.tw/Egbx

Last edit: 2017-10-26 10:40:24
2016-12-09 17:33:19
ez lát cắt nhỏ nhất
2016-11-15 10:18:35


























2016-09-27 02:59:43
Code AC:
http://shink.in/lS3NM
2015-11-15 09:30:03 Lollipop
k thể hiểu đc test ví dụ, test to thế này chắc chết
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.