题目描述

Yachiyo 有一张带权简单图，顶点有黑白两色。Yachiyo 可以做 $0$ 次或若干次操作，每次操作可以选择一条两端颜色不同的边，将其边权减 $1$ 且交换两端颜色。

Yachiyo 希望让图上所有点的边权相等，但是她希望所有操作结束之后，所有点的颜色都恢复到未进行操作时的初始状态。Yachiyo 想知道，最少需要进行多少次操作才可以达到她的要求。

输入格式

第一行一个正整数 $T$，代表数据组数。接下来 $T$ 组数据，每组数据的格式如下：

• 第一行两个正整数 $n,m$，分别代表图的点数和边数；
• 接下来一行 $n$ 个整数，第 $i$ 个整数 $c_i$ 代表编号为 $i$ 的点的颜色。$0$ 代表白色，$1$ 代表黑色。
• 接下来 $m$ 行，第 $i$ 行三个整数 $x_i,y_i,w_i$，代表图中有一条 $x_i,y_i$ 的边，边权为 $w_i$。

输出格式

对于每组数据，输出一行一个整数，代表最少需要的操作次数。如果无法满足 Yachiyo 的要求，输出 $-1$。

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

5
-1
-1
300

数据范围

• 对于 $30\%$ 的数据，$w_i \le 10$；
• 对于另外 $30\%$ 的数据，保证 $m = n-1$，输入的图是一棵树；
• 对于 $100\%$ 的数据：
  • $1 \le T \le 10^5$；
  • $1 \le n, \sum n \le 10^5$，$1 \le m, \sum m \le 5 \cdot 10^5$；
  • 对于所有的 $1 \le i \le n$：$c_i \in \{0,1\}$；
  • 对于所有的 $1 \le i \le m$：$0 \le w_i \le 10^9$，$1 \le x_i, y_i \le n$；
  • 数据保证输入的图中没有重边，输入的颜色只有 $0$ 和 $1$。