output_description: Print the maximum flow.
input_description: A flow network is given in the following format.
  
  $|V|\;|E|$  
  $u_0\;v_0\;c_0$  
  $u_1\;v_1\;c_1$  
  :  
  $u_{|E|-1}\;v_{|E|-1}\;c_{|E|-1}$  
    
  
  $|V|$, $|E|$ is the number of vertices and edges of the flow network
  respectively. The vertices in $G$ are named with the numbers 0, 1,...,
  $|V|-1$. The source is 0 and the sink is $|V|-1$.
  
  $u_i$, $v_i$, $c_i$ represent $i$-th edge of the flow network. A pair of $u_i$
  and $v_i$ denotes that there is an edge from $u_i$ to $v_i$ and $c_i$ is the
  capacity of $i$-th edge.
attempt: # import sys
  # input = sys.stdin.readline
  from collections import defaultdict
  
  INF = 10**9
  
  
  def dfs_for_Ford_Fulkerson(N, E, capacity, s, g, flowing):
      stack = [(s, INF)]
      root = [0] * N
      root[s] = -1
      V = [False] * N
      V[s] = True
      while stack:
          # print(stack)
          u, flow = stack.pop()
          # print(u, E[u])
          for v in E[u]:
              # print(v)
              # print(V[v])
              # print(v, not V[v], capacity[(u,v)]>0)
              if not V[v] and capacity[(u, v)] > 0:
                  root[v] = u
                  V[v] = True
                  if v == g:
                      if capacity[(u, v)] < flow:
                          flow = capacity[(u, v)]
                      break
                  stack.append((v, min(flow, capacity[(u, v)])))
          else:
              continue
          break
      else:
          return False
      ## 更新
      now = g
      while now != s:
          before = root[now]
          capacity[(before, now)] -= flow
          capacity[(now, before)] += flow
          now = before
      flowing[0] += flow
      # print(capacity, flow)
      return True
  
  
  def Ford_Fulkerson(N, E, capacity, s, g):
      flowing = [0]
      while dfs_for_Ford_Fulkerson(N, E, capacity, s, g, flowing):
          pass
      return flowing[0]
  
  
  def main():
      N, M = map(int, input().split())
      E = [[] for _ in range(N)]
      capacity = defaultdict(int)
      for i in range(M):
          u, v, c = map(int, input().split())
          E[u].append(v)
          capacity[(u, v)] = c
          E[v].append(u)
  
      print(Ford_Fulkerson(N, E, capacity, 0, N - 1))
  
  
  if __name__ == "__main__":
      main()
  
problem_description: Maximum Flow
  
  A flow network is a directed graph which has a $source$ and a $sink$. In a
  flow network, each edge $(u, v)$ has a capacity $c(u, v)$. Each edge receives
  a flow, but the amount of flow on the edge can not exceed the corresponding
  capacity. Find the maximum flow from the $source$ to the $sink$.
samples: [{"input": "4 5\n    0 1 2\n    0 2 1\n    1 2 1\n    1 3 1\n    2 3 2", "output": "3"}]