← 返回题目列表

AtCoder · tessoku_book_bp

A68. 最大流量

中文机器翻译题面 查看原题

配点: 1000 点

問題文

N 坦克和 M 有一个管道,j 主管是水箱 来自 A_j 的坦克 每秒朝 B_j 方向 C_j 最多可流过升水。
坦克 1 的坦克 每秒朝 N 每秒可以流多少升水?但是,您可以假设您无法在水箱中储存水。

制約

  • 2 \leq N \leq 400
  • 1 \leq M \leq 400
  • 1 \leq A_j , B_j \leq N
  • A_j \neq B_j
  • j\neq k 如果 (A_j,B_j) \neq (A_k,B_k)
  • 0 \leq C_j \leq 5000
  • 答案是 不超过 5000 的整数 给出了
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1 C_1
\vdots
A_M B_M C_M

出力

请以整数形式输出每秒可流动的最大升数。


入力例 1

6 7
1 2 5
1 4 4
2 3 4
2 5 7
3 6 3
4 5 3
5 6 5

出力例 1

8