Максимальный поток

Input

Первая строка содержит два целых числа $n$ и $m$ (1 \leq n \leq 100, 1 \leq m \leq 10000) — количество вершин и рёбер в сети соответственно. Каждая из последующих $m$ строк содержит три целых числа u_i, v_i и c_i (1 \leq u_i, v_i \leq n, 1 \leq c_i \leq 10000), означающих, что между вершинами u_i и v_i существует ребро с пропускной способностью c_i. Вершина $1$ — исток, вершина $n$ — сток. Граф сети неориентированный и может содержать кратные рёбра. Все входные числа — целые.

Output

Выведите максимальный поток в заданной сети.

Examples