你估下發生咩事？喺 6202 年，小青魚個群迎嚟咗佢嘅第 $10^6$ 位群友！未聽過？呢個群又叫做 Qingyu 嘅群，係佢班朋友吹水傾演算法競賽、非演算法競賽、北大笑話、北京美食同埋幾乎所有其他話題嘅地方。不過最重要嘅係，個群每日都充滿住關於邊個係邊個偶像嘅訊息。

按照傳統，小青魚正喺度搞緊一場有 $n$ 位群友參加嘅偶像派對，群友編號由 $1$ 到 $n$。呢班群友之間一共有 $m$ 條粉絲—偶像關係：喺第 $i$ 條關係入面，群友 $u_i$ 係群友 $v_i$ 嘅粉絲，而且由 $u_i$ 送畀 $v_i$ 嘅一份禮物成本係 $w_i$。喺派對上面，每位群友都必須送恰好一份特別禮物畀自己嘅其中一位偶像。不過，兩位群友互相送禮畀對方會好尷尬（雖然聽落都幾甜 :p），所以任何一對群友都唔可以互相送禮畀對方。

請搵出禮物嘅最小總成本，或者判斷唔存在合法嘅送禮安排。

輸入格式

第一行包含一個整數 $T$（$1 \le T$），代表測試資料嘅組數。接住落嚟係各組測試資料嘅描述。

每組測試資料嘅第一行包含兩個整數 $n$ 同 $m$（$1 \le n \le 10^6$，$0 \le m \le 10^6$），分別代表群友嘅數量同埋粉絲—偶像關係嘅數量。

接住落嚟 $m$ 行入面嘅第 $i$ 行包含三個整數 $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$。每個答案單獨佔一行。

範例

輸入格式 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$ 送禮畀群友 $2$，群友 $2$ 送禮畀群友 $3$，群友 $3$ 送禮畀群友 $1$。總成本係 $1 + 2 + 3 = 6$。

喺第二組範例測試資料入面，群友 $1$ 同 $2$ 焗住要互相送禮畀對方，所以唔存在合法嘅送禮安排。

喺第三組範例測試資料入面，群友 $1$ 送禮畀群友 $3$，群友 $2$ 送禮畀群友 $1$，群友 $3$ 送禮畀群友 $2$。總成本係 $1$。