{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE RecordWildCards  #-}
module Main where
import           Data.Maybe
import           Data.Traversable
import qualified Data.Vector         as V
import Data.Vector (Vector,(!))
import           Data.Vector.Mutable as MV
import           Prelude             as P
import Control.Monad
import Data.List
getInts :: IO [Int]
getInts = P.map P.read . words <$> getLine
printGraph g = V.forM_ g $ \v -> do
  putStrLn $ intercalate " " $ map show $ V.toList v
  
main :: IO ()
main = do
  v:e:_ <- getInts
  cs <- MV.new $ 2 * e
  g <- V.map (V.fromList . reverse . fst) <$> (V.freeze =<< genGraph v e cs)
  -- print =<< V.freeze cs
  r <- maxFlow 0 (v - 1) g cs
  print r
  --printGraph g
  where
    genGraph v e cs = do
      g <- MV.replicate v ([],0)
      forM_ [0 .. e - 1] $ \i -> do
        u:v:c:_ <- getInts
        MV.write cs i c
        MV.write cs (e+i) 0
        (es,s) <- MV.read g u
        (rs,sr) <- MV.read g v
        write g u (Edge v sr i :es,s+1)
        write g v (Edge u s (e+i):rs,sr+1)
        return ()
      return g
      
maxFlow :: Int -> Int -> Graph -> IOVector Int -> IO Int
maxFlow s t g cs = loop 0
  where
    loop f = do
      used <- MV.replicate (V.length g) False
      df <- dfs maxBound t g s cs used
      if df == 0
        then return f
        else loop (f + df)
         
data Edge = Edge
  { to    :: {-# UNPACK #-} !Int
  , revIx :: {-# UNPACK #-}!Int
  , capIx :: {-# UNPACK #-} !Int
  } deriving Show
type Graph = Vector (Vector Edge)

dfs :: Int -> Int -> Graph -> Int
    -> IOVector Int -> IOVector Bool
    -> IO Int
dfs f t g v cs used
  | v == t = return f
  | otherwise = do
      MV.write used v True
      fromMaybe 0 <$> loop
      where
        loop = flip untilJustM (g ! v) $ \e ->  do
          c <- MV.read cs   (capIx e)
          u <- MV.read used (to e)
          --putStrLn $ show e ++ ", (c,u):)" ++ show (c,u)
          if c <= 0 || u
            then return Nothing
            else do
            d <- dfs (min f c) t g (to e) cs used
            if d > 0
              then do
              MV.modify cs (subtract d) $ capIx e
              MV.modify cs (+d) $ capIx $ g ! to e ! revIx e
              return $ Just d
              else return Nothing


untilJustM ::
  Monad m => (a1 -> m (Maybe a)) -> Vector a1 -> m (Maybe a)
untilJustM f xs
  | V.null xs = return Nothing
  | otherwise = do
      x <- f (V.head xs)
      case x of
        Nothing -> untilJustM f $ V.tail xs
        Just _  -> return x