package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var infty = 1000000000

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

type DirectedGraphNodeID int

func newDirectedGraph(nNodes int) *DirectedGraph {
	graph := DirectedGraph{}

	graph.nodes = make([]*DirectedGraphNode, nNodes)
	for iNode := 0; iNode < nNodes; iNode++ {
		graph.nodes[iNode] = &DirectedGraphNode{
			key:       DirectedGraphNodeID(iNode),
			adjacents: map[DirectedGraphNodeID]*DirectedGraphNode{},
			costs:     map[DirectedGraphNodeID]int{},
			flows:     map[DirectedGraphNodeID]int{},
			visited:   false,
			d:         infty,
		}
	}

	return &graph
}

type DirectedGraph struct {
	nodes []*DirectedGraphNode
}

func (graph *DirectedGraph) sedAdjacent(leftIdx, rightIdx DirectedGraphNodeID, cost int) {
	graph.nodes[leftIdx].adjacents[rightIdx] = graph.nodes[rightIdx]
	graph.nodes[leftIdx].costs[rightIdx] = cost
	graph.nodes[leftIdx].flows[rightIdx] = 0
}

type DirectedGraphNode struct {
	key       DirectedGraphNodeID
	adjacents map[DirectedGraphNodeID]*DirectedGraphNode
	costs     map[DirectedGraphNodeID]int
	flows     map[DirectedGraphNodeID]int

	parent  *DirectedGraphNode
	visited bool
	d       int

	adjacentsForBFS []*DirectedGraphNode
}

type QueueEntry struct {
	node *DirectedGraphNode
	next *QueueEntry
}

type Queue struct {
	head, tail *QueueEntry
}

func (q *Queue) enqueue(node *DirectedGraphNode) {
	entry := QueueEntry{}
	entry.node = node

	if q.tail == nil {
		q.head = &entry
		q.tail = &entry
		return
	}

	q.tail.next = &entry
	q.tail = q.tail.next
}

func (q *Queue) dequeue() *QueueEntry {
	if q.head == nil {
		return nil
	}
	poped := q.head
	q.head = q.head.next
	if q.head == nil {
		q.tail = nil
	}
	return poped
}

func (q *Queue) isEmpty() bool {
	return q.head == nil
}

func getResidualCapacity(u, v *DirectedGraphNode) int {
	_, uToV := u.adjacents[v.key]
	_, vToU := v.adjacents[u.key]

	if uToV {
		return u.costs[v.key] - u.flows[v.key]
	} else if vToU {
		return v.flows[u.key]
	}
	return 0
}

func fillDistancesByBreadthFirstSearch(graph *DirectedGraph, startNodeID, endNodeID DirectedGraphNodeID) {
	// reset
	for _, node := range graph.nodes {
		node.parent = nil
		node.visited = false
		node.d = infty

		node.adjacentsForBFS = []*DirectedGraphNode{}
	}

	for _, u := range graph.nodes {
		for _, v := range u.adjacents {
			residualCapacity1 := getResidualCapacity(u, v)
			if residualCapacity1 > 0 {
				u.adjacentsForBFS = append(u.adjacentsForBFS, v)
			}
			residualCapacity2 := getResidualCapacity(v, u)
			if residualCapacity2 > 0 {
				v.adjacentsForBFS = append(v.adjacentsForBFS, u)
			}
		}
	}

	startNode := graph.nodes[startNodeID]

	startNode.visited = true
	startNode.d = 0

	queue := Queue{}
	queue.enqueue(startNode)
	for !queue.isEmpty() {
		u := queue.dequeue().node
		for _, adjacent := range u.adjacentsForBFS {
			if !adjacent.visited {
				adjacent.visited = true
				adjacent.d = u.d + 1
				adjacent.parent = u
				queue.enqueue(adjacent)
			}
		}
		u.visited = true
	}
}

func getPathInResidualNetwork(graph *DirectedGraph, startNodeID, endNodeID DirectedGraphNodeID) []*DirectedGraphNode {
	fillDistancesByBreadthFirstSearch(graph, startNodeID, endNodeID)

	startNode := graph.nodes[startNodeID]
	endNode := graph.nodes[endNodeID]
	if endNode.parent == nil {
		return []*DirectedGraphNode{}
	}

	current := endNode
	path := []*DirectedGraphNode{}
	for {
		path = append(path, current)
		if current == startNode {
			break
		}
		if current.parent == nil {
			return []*DirectedGraphNode{}
		}
		current = current.parent
	}

	for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
		path[i], path[j] = path[j], path[i]
	}

	return path
}

func getCriticalPathCost(path []*DirectedGraphNode) int {
	minimum := 2 * 10000
	for i := 0; i < len(path)-1; i++ {
		u := path[i]
		v := path[i+1]
		uvCost := getResidualCapacity(u, v)
		if minimum > uvCost {
			minimum = uvCost
		}

		// fmt.Print(uvCost, " ")
	}
	// fmt.Print("\n")
	return minimum
}

func fordFulkerson(graph *DirectedGraph, startNodeID, endNodeID DirectedGraphNodeID) {
	for _, l := range graph.nodes {
		for _, r := range l.adjacents {
			l.flows[r.key] = 0
		}
	}

	for {
		path := getPathInResidualNetwork(graph, startNodeID, endNodeID)
		if len(path) == 0 {
			break
		}

		costOfCriticalEdge := getCriticalPathCost(path)

		// for _, v := range path {
		// 	fmt.Print(v.key, " ")
		// }
		// fmt.Print("\n")
		// fmt.Println(costOfCriticalEdge)

		for i := 0; i < len(path)-1; i++ {
			u := path[i]
			v := path[i+1]
			if u.costs[v.key] > 0 {
				u.flows[v.key] += costOfCriticalEdge
			} else {
				v.flows[u.key] -= costOfCriticalEdge
			}
		}
	}
}

func main() {
	scanner.Split(bufio.ScanWords)

	nNodes := nextInt()
	nEdges := nextInt()

	graph := newDirectedGraph(nNodes)

	for iEdge := 0; iEdge < nEdges; iEdge++ {
		leftNodeIdx := DirectedGraphNodeID(nextInt())
		rightNodeIdx := DirectedGraphNodeID(nextInt())
		cost := nextInt()
		graph.sedAdjacent(leftNodeIdx, rightNodeIdx, cost)
	}

	startNodeID := DirectedGraphNodeID(0)
	endNodeID := DirectedGraphNodeID(nNodes - 1)
	fordFulkerson(graph, startNodeID, endNodeID)

	totalFlow := 0
	for _, f := range graph.nodes[startNodeID].flows {
		totalFlow += f
	}

	fmt.Println(totalFlow)
}



Measured memory_bytes: 1848