AZY有一天去某幼儿园做volunteer，为了博得小盆友们的欢心，他打算先去WALMART买些toys，幼儿园里有n+m个小盆友，其中n个是女孩。
AZY要给每个child一个玩具，每个玩具都需要1000元，但女生和男生之间是存在relationship（暂且称为好感度）这个东西的，如果女孩x和男孩y有值为d的好感度，且已经给他们二人中的一个买了toy，那么另一个人的toy只需花1000-d元即可。请你帮他看看，最少需要多少money可以给孩子们买完玩具。当然了，only one relationship can be used when buying for one kid.
输入的第一行为一个整数，测试数据的组数，不超过10
每组数据，第一行有三个整数，N, M, R.
接下来R行， 每行三个整数，xi, yi, di，表示编号为xi的女孩与yi的男孩之间存在值为di的好感度。
每组数据之前有一个空行。
1 ≤ N, M ≤ 1000
0 ≤ R ≤ 50,000
0 ≤ xi < N
0 ≤ yi < M
0 < di < 1000
对于每组数据，输出一行，为最少需要花的钱。
1
2 2 4
0 0 1
0 1 2
1 0 25
1 1 303943