Scanf.scanf "%d" (fun t ->
    let module S = Set.Make (struct type t = int * int let compare = compare end) in
    for i = 1 to t do
        Scanf.scanf " %d" (fun n ->
            let klr = Array.init n (fun _ -> Scanf.scanf " %d %d %d" (fun k l r -> k, l, r)) in
            let sum = Array.fold_left (fun acc (_, l, r) -> acc + min l r) 0 klr in

            let rec loop i left right =
                if i = n then Array.of_list left, Array.of_list right else
                    let k, l, r = klr.(i) in
                    if l > r then loop (i + 1) ((k, l - r) :: left) right
                             else loop (i + 1) left ((n - k, r - l) :: right)
            in
            let left, right = loop 0 [] [] in
            Array.sort compare left;
            Array.sort compare right;
            let proc a =
                let len = Array.length a in
                let rec loop i j acc set ct =
                    if i = len then acc else
                        let k, dif =  a.(i) in
                        if k > j then loop i (j + 1) acc set ct else
                            let set = S.add (dif, i) set in
                            let ct = ct + 1 in
                            let acc = acc + dif in
                            if ct <= k then loop (i + 1) j acc set ct else
                                let ((dif, _) as m) = S.min_elt set in
                                let set = S.remove m set in
                                let ct = ct - 1 in
                                let acc = acc - dif in
                                loop (i + 1) j acc set ct
                in
                loop 0 0 0 S.empty 0
            in
            Printf.printf "%d\n" @@ sum + proc left + proc right
        )
    done
)