흐름

무한한 네트워크에서의 최대 유량 문제를 다룹니다. 양쪽 부분에 각각 $n$개의 정점이 있는 이분 그래프 $G$와 $m$개의 유향 간선이 주어집니다. 각 간선은 왼쪽 부분에서 오른쪽 부분으로 향하며, 용량이 정해져 있습니다.

다음 절차로 네트워크의 族 $\\{F_k\\}$를 만듭니다.

• $G$의 복사본을 $k$개 만들고, 이를 $G_1, G_2, \\ldots, G_k$라고 합니다.
• 모든 $1 \\leq i \\leq k - 1$와 $1 \\leq u \\leq n$에 대해, $G_i$ 오른쪽 부분의 $u$번째 정점에서 $G_{i + 1}$ 왼쪽 부분의 $u$번째 정점으로 용량이 무한대인 간선을 추가합니다.
• 소스에서 $G_1$ 왼쪽 부분의 모든 정점으로 용량이 무한대인 간선을 추가합니다.
• $G_k$ 오른쪽 부분의 모든 정점에서 싱크로 용량이 무한대인 간선을 추가합니다.

$F_k$의 최대 유량을 $f_k$라고 합니다. $k$가 무한대로 갈 때 수열 $\\{f_k\\}$가 어떻게 되는지 구하세요. 일정한 값으로 수렴하지 않으면 $-1$을 출력합니다. 수렴하면 $\\lim_{k \\to +\\infty} f_k$를 출력합니다.

첫째 줄에 정수 $n$과 $m$이 주어집니다 ($1 \\leq n \\leq 2000$, $1 \\leq m \\leq 4000$).

이후 $m$개의 줄에는 정수 $u$, $v$, $w$가 주어집니다 ($1 \\leq u, v \\leq n$, $1 \\leq w \\leq 10^5$). 이는 왼쪽 부분의 $u$번째 정점에서 오른쪽 부분의 $v$번째 정점으로 용량이 $w$인 유향 간선이 있다는 뜻입니다.

$\\{f_k\\}$가 일정한 값으로 수렴하지 않으면 $-1$을 출력합니다. 그렇지 않으면 $\\lim_{k \\to +\\infty} f_k$를 출력합니다.