なんと、西暦 6202 年に Little Cyan Fish のサーバーが $10^6$ 人目のメンバーを迎えました！聞いたことがありませんか？実はこのサーバーは Qingyu のグループとしても知られており、彼の友人たちが集まって競技プログラミングや競技プログラミング以外の話題、北京大学のジョーク、北京のグルメ、その他ありとあらゆることについて語り合う場所なのです。しかし何より重要なのは、誰が誰のアイドルであるかについてのメッセージで毎日チャットが溢れかえっていることです。

伝統に従い、Little Cyan Fish は $1$ から $n$ までの番号が付けられた $n$ 人のメンバーでアイドルパーティーを開催することにしました。これらのメンバーの間には $m$ 個のファン・アイドル関係があります。$i$ 番目の関係では、メンバー $u_i$ はメンバー $v_i$ のファンであり、$u_i$ から $v_i$ へのプレゼントには $w_i$ の費用がかかります。パーティーでは、各メンバーは自分のアイドルのうちの 1 人にちょうど 1 つの特別なプレゼントを贈らなければなりません。しかし、2 人のメンバーが互いにプレゼントを贈り合うのは気まずいため（それはそれでとても素敵に聞こえますが :p）、どの 2 人のメンバーも互いにプレゼントを贈り合うことはできません。

プレゼントの総費用の最小値を求めるか、条件を満たす贈り方が存在しないことを判定してください。

入力

最初の行には、テストケースの個数を表す整数 $T$（$1 \le T$）が与えられます。続いて各テストケースの説明が与えられます。

各テストケースの最初の行には、メンバーの人数とファン・アイドル関係の個数をそれぞれ表す 2 つの整数 $n$ と $m$（$1 \le n \le 10^6$、$0 \le m \le 10^6$）が与えられます。

続く $m$ 行のうち $i$ 行目には、3 つの整数 $u_i$、$v_i$、$w_i$（$1 \le u_i, v_i \le n$、$u_i \ne v_i$、$0 \le w_i \le 10^9$）が与えられます。これはメンバー $u_i$ がメンバー $v_i$ のファンであり、$u_i$ から $v_i$ へのプレゼントに $w_i$ の費用がかかることを表します。

すべてのテストケースにおける $n$ の総和は $10^6$ を超えず、すべてのテストケースにおける $m$ の総和も $10^6$ を超えないことが保証されます。各テストケースにおいて、各順序対 $(u_i, v_i)$ は高々 1 回しか現れないことが保証されます。2 人のメンバーが互いに相手のファンである場合もあります。

出力

各テストケースについて、プレゼントの総費用の最小値を表す整数を出力してください。条件を満たす贈り方が存在しない場合は $-1$ を出力してください。各答えはそれぞれ別の行に出力してください。

入出力例

入力 1

3
3 3
1 2 1
2 3 2
3 1 3
2 2
1 2 0
2 1 0
3 4
1 2 0
1 3 1
2 1 0
3 2 0

出力 1

6
-1
1

注記

1 番目のサンプルテストケースでは、メンバー $1$ がメンバー $2$ に、メンバー $2$ がメンバー $3$ に、メンバー $3$ がメンバー $1$ にプレゼントを贈ります。総費用は $1 + 2 + 3 = 6$ です。

2 番目のサンプルテストケースでは、メンバー $1$ と $2$ が互いにプレゼントを贈り合わなければならなくなるため、条件を満たす贈り方は存在しません。

3 番目のサンプルテストケースでは、メンバー $1$ がメンバー $3$ に、メンバー $2$ がメンバー $1$ に、メンバー $3$ がメンバー $2$ にプレゼントを贈ります。総費用は $1$ です。