애드몬드-카프

$1$부터 $N$까지 번호가 붙은 $N$개의 정점과 $M$개의 방향 간선으로 이루어진 그래프가 있다.

각 간선에는 해당 간선으로 보낼 수 있는 유량의 최댓값인 용량이 정해져 있다.

시작 정점 $S$에서 도착 정점 $T$로 유량을 보내려고 한다.

각 간선으로 보내는 유량은 해당 간선의 용량을 넘을 수 없으며, $S$와 $T$를 제외한 모든 정점에서는 들어오는 유량의 합과 나가는 유량의 합이 같아야 한다.

$S$에서 $T$로 보낼 수 있는 유량의 최댓값을 구하라.

첫 번째 줄에 정점의 개수 $N$, 간선의 개수 $M$, 시작 정점 $S$, 도착 정점 $T$가 주어진다. $(2 \leq N \leq 100, 0 \leq M \leq 500, 1 \leq S,T \leq N, S \neq T)$

두 번째 줄부터 $M$개의 줄에 걸쳐 방향 간선을 나타내는 세 정수 $u$, $v$, $c$가 주어진다. $(1 \leq u,v \leq N, u \neq v, 1 \leq c \leq 10^9)$

이는 $u$번 정점에서 $v$번 정점으로 최대 $c$만큼의 유량을 보낼 수 있다는 뜻이다.

같은 방향 간선은 두 번 이상 주어지지 않는다.

$S$에서 $T$로 보낼 수 있는 유량의 최댓값을 출력한다.