题目内容

多多需要处理 $T$ 套告警网络，每套网络由 $N$ 个节点和 $N$ 条无向边组成，没有自环和重边，并且任意两个节点之间都可以互相直达。

因此，这条网络中恰好存在一个简单环。

节点 $i$ 的初始告警状态为 $b_i$：

• $b_i = 0$ 表示告警已关闭；
• $b_i = 1$ 表示告警正在响起。

第 $i$ 条边连接节点 $u_i, v_i$，维护这条边需要花费 $c_i$。维护一条边时，它两个端点的告警状态都会翻转：$0$ 变为 $1$，$1$ 变为 $0$。

一份维护方案是一个边的集合。集合中的每条边恰好维护一次，未被选中的边不进行维护。维护顺序不会影响最终状态，也不认为不同方案。

如果一份方案执行后所有节点的告警状态都变为 $0$，则称它是可行方案。

可行方案的费用是其中所有边的维护费用之和。

请帮多多计算：

1. 可行方案的最小费用；
2. 费用最小的可行方案数量。

输入描述

第一行包含一个整数 $T$，表示测试用例数量。

对于每个测试用例：

第一行包含一个整数 $N$，表示节点数量。

第二行包含 $N$ 个整数 $b_1,b_2,\dots,b_N$，表示各节点的初始告警状态。

接下来 $N$ 行，第 $i$ 行包含三个整数 $u_i, v_i, c_i$，表示第 $i$ 条边连接节点 $u_i, v_i$，维护费用为 $c_i$。

输出描述

对于每个测试用例输出一行。

如果不存在可行方案，输出 $-1\ 0$；

否则输出两个整数，依次表示最小费用和费用最小的可行方案数量。

补充说明

$1 \le T \le 3$ $3 \le N \le 2 * 10^5$ $b_i \in \{0,1\}$ $1 \le u_i,v_i \le N,\ u_i \ne v_i$ $1 \le c_i \le 10^9$ 输入的图联通，不含自环和重边。

样例1

输入

3
5
0 1 1 1 1
1 2 4
2 3 2
3 1 7
3 4 5
4 5 1
4
1 1 1 1
1 2 1
2 3 1
3 4 1
4 1 1
3
1 0 0
1 2 1
2 3 1
3 1 1

输出

3 1
2 2
-1 0

说明

第一个测试用例选择第 $2、5$ 条边，费用为 $3$，另一份可行方案费用为 $12$，因此答案为 $3\ 1$。