Curiosamente, incluso a mí me resulta extraño que, aunque parece una regla natural que considerar, ni siquiera haya podido encontrar un solo ejemplo de que existiera antes. Algún que otro problema incluso se le parece un poco, pero aun así, ninguno es exactamente igual. Qué extraño. O par.

— Sam Cappleman-Lynes

Se te da un grafo no dirigido con $n$ vértices y $m$ aristas. Supongamos que $T$ es un árbol generador de este grafo y denotemos con $\mathrm{Cost}(T)$ la suma de los pesos de todas las aristas de $T$. Encuentra $T_1$ y $T_2$ tales que:

• $\mathrm{Cost}(T_1)$ sea par y $\mathrm{Cost}(T_1)$ sea mínimo.
• $\mathrm{Cost}(T_2)$ sea impar y $\mathrm{Cost}(T_2)$ sea mínimo.

Entrada

La primera línea contiene un único entero $T$ ($1 \le T \le 10^4$), el número de casos de prueba. Para cada caso de prueba:

La primera línea contiene dos enteros $n$ y $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 5 \cdot 10^5$), que indican el número de vértices y el número de aristas.

Cada una de las siguientes $m$ líneas contiene tres enteros $u_i, v_i$ y $w_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$, $1 \le w_i \le 10^9$), que describen una arista no dirigida.

Se garantiza que la suma de todos los $n$ es como máximo $2 \cdot 10^5$ y la suma de todos los $m$ es como máximo $5 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime una línea con dos enteros: $\mathrm{Cost}(T_1)$ y $\mathrm{Cost}(T_2)$. Si no puedes encontrar un árbol generador de ese tipo, imprime -1 como su coste.

Ejemplos

Entrada 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

Salida 1

-1 5
-1 -1
4 3