我们正在考虑一个无限网络上的最大流问题。

给定一个二分图 $G$，其左右两部分各有 $n$ 个顶点，共有 $m$ 条有向边。每条边从左侧指向右侧，并具有指定的容量。我们希望构造一个网络族 $\{F_k\}$。

以下是构造网络 $F_k$ 的步骤：

• 首先，我们生成 $k$ 个图 $G$ 的副本，分别记为 $G_1, G_2, \dots, G_k$。
• 对于所有 $1 \le i \le k - 1$ 和 $1 \le u \le n$，我们添加一条从 $G_i$ 右侧第 $u$ 个顶点到 $G_{i+1}$ 左侧第 $u$ 个顶点的有向边，容量为无穷大。
• 我们添加从源点到 $G_1$ 左侧所有顶点的有向边，容量为无穷大。
• 我们添加从 $G_k$ 右侧所有顶点到汇点的有向边，容量为无穷大。

设 $f_k$ 为网络 $F_k$ 中的最大流。

我们想知道当 $k$ 趋于无穷大时，序列 $\{f_k\}$ 的表现。如果 $\{f_k\}$ 不收敛于一个常数，输出 $-1$。否则，输出 $\lim_{k \to +\infty} f_k$。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 2000, 1 \le m \le 4000$)。

接下来 $m$ 行，每行包含三个整数 $u, v$ 和 $w$ ($1 \le u, v \le n, 1 \le w \le 10^5$)，表示存在一条从左侧第 $u$ 个顶点到右侧第 $v$ 个顶点的有向边，容量为 $w$。

输出格式

如果序列 $\{f_k\}$ 不收敛于一个常数，输出 $-1$。否则，输出 $\lim_{k \to +\infty} f_k$。

样例

输入 1

5 5
1 2 3
2 3 4
3 1 2
4 5 6
5 4 3

输出 1

12