import random
import time
from collections import defaultdict, deque


def solve_dfs(n, m, edges):
    graph: list[dict[int, int]] = [defaultdict(int) for _ in range(n)]
    capacities: list[dict[int, int]] = [defaultdict(int) for _ in range(n)]
    for _ in range(m):
        u, v, w = edges[_]
        graph[u][v] = 0
        capacities[u][v] += w
    source, sink = 0, n-1

    ans: int = 0
    while True:
        # Run BFS to find shortest s-t path
        parent: list[int] = [-1] * n
        parent[0] = -2
        queue: deque[tuple[int, int]] = deque([(source, 10**18)])
        while queue:
            u, flow = queue.popleft()
            for v in graph[u]:
                if parent[v] == -1 and capacities[u][v] > graph[u][v]:
                    parent[v] = u
                    if v == sink:
                        max_capacity = min(flow, capacities[u][v] - graph[u][v])
                        break
                    queue.append((v, min(flow, capacities[u][v] - graph[u][v])))
        if parent[sink] == -1:
            # We didn't find au augmenting path
            break
        v = sink
        while v != source:
            graph[parent[v]][v] += max_capacity  # noqa
            graph[v][parent[v]] -= max_capacity  # noqa
            v = parent[v]
        ans += max_capacity

    return ans

def solve_bfs(n, m, edges):
    graph: list[dict[int, int]] = [defaultdict(int) for _ in range(n)]
    capacities: list[dict[int, int]] = [defaultdict(int) for _ in range(n)]
    for _ in range(m):
        u, v, w = edges[_]
        graph[u][v] = 0
        capacities[u][v] += w
    source, sink = 0, n-1

    ans: int = 0
    while True:
        # Run DFS to find an augmenting s-t path (hopefully will be bad)
        parent: list[int] = [-1] * n
        parent[0] = -2
        stack: list[tuple[int, int]] = [(source, 10**18)]
        while stack:
            u, flow = stack.pop()
            for v in graph[u]:
                if parent[v] == -1 and capacities[u][v] > graph[u][v]:
                    parent[v] = u
                    if v == sink:
                        max_capacity = min(flow, capacities[u][v] - graph[u][v])
                        break
                    stack.append((v, min(flow, capacities[u][v] - graph[u][v])))
        if parent[sink] == -1:
            # We didn't find au augmenting path
            break
        v = sink
        while v != source:
            graph[parent[v]][v] += max_capacity  # noqa
            graph[v][parent[v]] -= max_capacity  # noqa
            v = parent[v]
        ans += max_capacity

    return ans


for _ in range(100000000):
    # Create random inputs
    n = random.randint(2, 10)
    m = random.randint(1, 20)
    edges = [(random.randint(0, n-1), random.randint(0, n-1), random.randint(0, 10**9)) for _ in range(m)]

    start_time = time.time()
    solve_bfs(n, m, edges)
    bfs_time = time.time() - start_time

    start_time = time.time()
    solve_dfs(n, m, edges)
    dfs_time = time.time() - start_time

    if dfs_time > 0.8 and bfs_time < 0.5:
        print(n, m, edges)
        print("DFS:", dfs_time)
        print("BFS:", bfs_time)
        print()