奇妙なことに、自然に考えられそうな規則であるにもかかわらず、以前に存在していた例を一つも見つけられないことは、私でさえ奇妙に思います。あちらこちらにある問題の中には少し似たものもありますが、それでも、まったく同じものは一つもありません。なんと奇妙な。あるいは偶数の。

— Sam Cappleman-Lynes

頂点数 $n$、辺数 $m$ の無向グラフが与えられます。$T$ をこのグラフの全域木とし、$\mathrm{Cost}(T)$ を $T$ に含まれるすべての辺の重みの総和とします。次の条件を満たす $T_1$ と $T_2$ を求めてください。

• $\mathrm{Cost}(T_1)$ が偶数で、$\mathrm{Cost}(T_1)$ が最小です。
• $\mathrm{Cost}(T_2)$ が奇数で、$\mathrm{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$ であることが保証されます。

出力

各テストケースについて、二つの整数 $\mathrm{Cost}(T_1)$ と $\mathrm{Cost}(T_2)$ を 1 行に出力してください。そのような全域木が見つからない場合は、そのコストの代わりに -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