#P17866. 偶像与粉丝

偶像与粉丝

H. 偶像与粉丝

有 nn 个人和 mm 条有向关系。关系 (ui,vi,wi)(u_i,v_i,w_i) 表示 uiu_i 可以向 viv_i 送礼,费用为 wiw_i。

每个人必须恰好向一个自己有关系指向的人送礼。禁止两个人相互送礼,即不能同时选择 u→vu\to v 和 v→uv\to u。

求满足要求的最小总费用;无解时输出 −1-1。

输入格式

第一行测试组数 T≥1T\ge1。每组第一行 n,mn,m,随后 mm 行,每行三个整数 ui,vi,wiu_i,v_i,w_i。

1≤n≤1061\le n\le10^6,0≤m≤1060\le m\le10^6,1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i,0≤wi≤1090\le w_i\le10^9。

同一组内每个有序对 (ui,vi)(u_i,v_i) 至多出现一次,可以同时存在两个相反方向的关系。所有测试的 nn 之和、mm 之和分别不超过 10610^6。

输出格式

每组输出一行最小总费用,或 −1-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

输出:

6
-1
1