#P17866. 偶像与粉丝
偶像与粉丝
H. 偶像与粉丝
有 个人和 条有向关系。关系 表示 可以向 送礼,费用为 。
每个人必须恰好向一个自己有关系指向的人送礼。禁止两个人相互送礼,即不能同时选择 和 。
求满足要求的最小总费用;无解时输出 。
输入格式
第一行测试组数 。每组第一行 ,随后 行,每行三个整数 。
,,,,。
同一组内每个有序对 至多出现一次,可以同时存在两个相反方向的关系。所有测试的 之和、 之和分别不超过 。
输出格式
每组输出一行最小总费用,或 。
样例 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