你猜怎麼著？在 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$。