你猜怎么着？在 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$。