#!/usr/bin/env ruby



$visited = []
$pre_vertex = []


def min a,b
  if a<b then return a else b end
end

def init_dfs v,e
  $visited = Array.new(v,false)
  $pre_vertex = Array.new(v,false)
end

#b -> e ??§edges
def dfs b,e,es
  es[b].each do |edge|
    if !$visited[edge[0]] and edge[1]>0 then
      $visited[edge[0]] = true
      $pre_vertex[edge[0]] = b
      dfs(edge[0],e,es)
    end
  end
end


def back_trace v,e,es
  flow =[]
  min_c = 10e8

  to = v-1
  from = $pre_vertex[v-1]
  flow=[[from,to]]+flow
  min_c = min(min_c,es[from].select{|i|i[0]==to}[0][1])

  while from != 0
    to = from
    from = $pre_vertex[from]
    flow=[[from,to]]+flow
    min_c = min(min_c,es[from].select{|i|i[0]==to}[0][1])
  end
  return flow,min_c
end



v_size,e_size = gets.chomp.split(/ /).map{|i| i.to_i}

edges = Array.new(v_size).map{ Array.new()}


e_size.times do
  u,v,c = gets.chomp.split(/ /).map{|i| i.to_i}
  edges[u]<<[v,c]
end

  @ans = 0
loop do
  init_dfs(v_size,e_size)
  dfs(0,v_size-1,edges)
  if $visited[v_size-1] then
    f,min_c = back_trace(v_size,e_size,edges)
    f.each do |i|
      ne = edges[i[0]].select{|ee|ee[0]==i[1]}[0]
      ne[1]=ne[1]-min_c
      edges[i[0]].select!{|ee|ee[0]!=i[1]}
      edges[i[0]]=edges[i[0]]<<ne
    end
    @ans = @ans+ min_c
  else
    p @ans
    break
  end
end