19022번 - Flow 다국어

문제

We are considering a maximum flow problem on an infinite network.

You are given a bipartite graph $G$ with $n$ vertices in both parts and $m$ directed edges. Each edge goes from the left part to the right part, and has its capacity specified. We want to construct a family of networks $\{F_k\}$.

Here are the steps to construct the network $F_k$.

• We first produce $k$ copies of the graph $G$. We call these copies $G_1, G_2, \ldots, G_k$.
• For all 1ドル \leq i \leq k - 1$ and 1ドル \leq u \leq n,ドル we add a directed edge from $u$-th vertex in the right part of $G_i$ to $u$-th vertex in the left part of $G_{i + 1}$ with infinite capacity.
• We add directed edges from the source to all the vertices in the left part of $G_1$ with infinite capacity.
• We add directed edges from all the vertices in the right part of $G_k$ to the sink with infinite capacity.

Let $f_k$ be the maximum flow in the network $F_k$.

We want to know what the sequence $\{f_k\}$ looks like when $k$ goes to infinity. If $\{f_k\}$ does not converge to a constant, output $-1$. Otherwise, output $\lim\limits_{k \to +\infty} f_k$.

입력

The first line contains two integers $n$ and $m$ (1ドル \leq n \leq 2000,ドル 1ドル \leq m \leq 4000$).

Each of the following $m$ lines contains three integers $u,ドル $v,ドル and $w$ (1ドル \leq u, v \leq n,ドル 1ドル \leq w \leq 10^5$) which indicate that there is a directed edge from the $u$-th vertex in the left part to the $v$-th vertex in the right part with capacity $w$.

출력

If the sequence $\{f_k\}$ does not converge to a constant, output $-1$. Otherwise, output $\lim\limits_{k \to +\infty} f_k$.

제한

힌트