给定一个包含 $n$ 个顶点和 $m$ 条边的无向图。假设 $T$ 是该图的一棵生成树，记 $\text{Cost}(T)$ 为 $T$ 中所有边的权重之和。请找到 $T_1$ 和 $T_2$ 使得：

• $\text{Cost}(T_1)$ 为偶数，且 $\text{Cost}(T_1)$ 最小。
• $\text{Cost}(T_2)$ 为奇数，且 $\text{Cost}(T_2)$ 最小。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。每个测试用例：

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 2 \cdot 10^5, 1 \le m \le 5 \cdot 10^5$)，分别表示顶点数和边数。

接下来的 $m$ 行，每行包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9$)，描述一条无向边。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$，所有测试用例的 $m$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行，包含两个整数：$\text{Cost}(T_1)$ 和 $\text{Cost}(T_2)$。注意，如果找不到对应的生成树，请输出 “-1” 作为其权重。

样例

输入 1

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

输出 1

-1 5
-1 -1
4 3