该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“赛后递交”以递交本题。

题目描述

小Z作为市长，要给两个辖区进行道路拓展的工作。

可以将城市看为由 $n$ 个点，$m$ 条边构成的图，其中每个点的管辖权为 $A$ 区或 $B$ 区，边权表示当前道路的宽度。

小Z的目标是让所有的路一样宽，即边权一样。每次可以挑选一条边，进行拓展工作，即边权+1，但是由于财政问题，如果这条路两端都是相同的辖区，成本花费太多就不愿意展开修路工作，即要两端处于不同的辖区才能展开修路工作。为了流动管理，在每一次修路之后，两端的辖区会更换管辖权，即原为 $A$ 区的点改为 $B$ 区，原为 $B$ 区的点改为 $A$ 区。

小Z需要知道，让所有道路都成为一样的宽度，并且保证最后的每个点管辖权与初始相同，最少的修路次数是多少。

若无法完成要求，输出 -1

输入格式

第一行，图中的点数 $n$ 与边数 $m$。

第二行，$n$ 个由 0 或 1 组成的数字，表示每个点初始的辖区。

接下来 $m$ 行，每行 $3$ 个数字，$u,v,w$，表示 $u$ 与 $v$ 之间有一条边权为 $w$ 的边

输出格式

如题意所求

输入输出样例

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

3

样例 $\tt \#1$说明

1. 操作 $1-3$ 边+1
2. 操作 $1-2$ 边+1
3. 操作 $2-3$ 边+1

最后所有边权为 $3$，并且每个点管辖区与输入时原图一致

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

-1

数据范围

$2\le n \le 10^5, 1\le m \le min(5\times 10^5, \frac{n\times (n-1)}2)$

$1\le u_i,v_i\le n,0\le w_i\le 10^9$

给定图保证为简单图（没有自环与重边）