Oddly, even I find it odd that even though this seems like a natural rule to consider, I haven't even been able to find a single example of it existing previously. The odd problem here and there even resembles it a little bit, but even so, none of them are quite the same. How odd. Or even.

— Sam Cappleman-Lynes

You are given an undirected graph with $n$ vertices and $m$ edges. Assume $T$ is a spanning tree of this graph, and let's denote $\mathrm{Cost}(T)$ as the total weights of all the edges in $T$. Please find $T_1$ and $T_2$ such that:

• $\mathrm{Cost}(T_1)$ is even, and $\mathrm{Cost}(T_1)$ is minimized.
• $\mathrm{Cost}(T_2)$ is odd, and $\mathrm{Cost}(T_2)$ is minimized.

Input

The first line contains a single integer $T$ ($1 \le T \le 10^4$), the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 5 \cdot 10^5$), denoting the number of vertices and the number of edges.

Each of the following $m$ lines contains three integers $u_i, v_i$ and $w_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$, $1 \le w_i \le 10^9$), describing an undirected edge.

It is guaranteed that the sum of all $n$ is at most $2 \cdot 10^5$, and the sum of all $m$ is at most $5 \cdot 10^5$.

Output

For each test case, output a single line containing two integers: $\mathrm{Cost}(T_1)$ and $\mathrm{Cost}(T_2)$. Note that if you can't find such a spanning tree, please print -1 as the cost instead.

Examples

Input 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

Output 1

-1 5
-1 -1
4 3