Bảo vệ


Submit solution

Points: 0.22 (partial)
Time limit: 1.5s
Memory limit: 512M

Problem type

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\) \(\left(N \leq 5000\right)\).

Các dòng tiếp theo cho đến hết file có không quá \(10000\) dòng, 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\) \(\left(s \leq 65000\right)\) quân để chặn địch trên đường này.

Output

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

Sample 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

Sample Output

79169

Comments

There are no comments at the moment.