      MODULE myQsortMod
! 構造型のクイックソート
! 問題に合わせてうまく流用するための元プログラム．
! メンバーsortObjについて，インデックスが小さいと小さい（昇順）

! 他の言語だとpairとかにあたるものを作りたい．
      implicit none
      integer, parameter, private :: p = 8
      
      type myData
        ! setter,getterは作らないで，メインプログラムから直接アクセス．
        
        ! ソートの基準
        integer(p) :: sortObj !
        ! その他のデータ
        integer(p) :: K,L,R
      end type myData
      
      interface Qsort
        module procedure :: myQsort
      end interface
      
      contains
      pure recursive function myQsort( a ) result( r )
        implicit none
        type(myData), intent(in) :: a(:)
        type(myData) :: r( size(a) )
        integer(p) :: sample(3), len ,i,j
        
        len = size( a )
        if( len<=1 )then
          r = a
        else
          !select pivot
          sample(1:3) = [a(1)%sortObj, a(len/2)%sortObj, a(len)%sortObj]
          do i = 1,2
            do j = 2,3
              if( sample(i)>sample(j) )then
                len = sample(i) !len is now buffer
                sample(i) = sample(j)
                sample(j) = len
              end if
            end do
          end do
          
          r = [ myQsort( pack(a(:), a(:)%sortObj< sample(2)) ), &
                         pack(a(:), a(:)%sortObj==sample(2))  , &
                myQsort( pack(a(:), a(:)%sortObj> sample(2)) ) ]
        end if
      end function myQsort
      end MODULE myQsortMod
      
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

      PROGRAM camelTrain
      use myQsortMod
      IMPLICIT NONE
      INTEGER,PARAMETER :: p = 8
      integer(p) :: t,n,c,i,ii,ans,anss(10**5)
      type(myData) :: camel(2*10**5)
      logical :: seat(2*10**5) = .false.
      
      read*,t
      
      do c = 1,t
        
        read*,n
        do i = 1,n
          read*,camel(i)%K,camel(i)%l,camel(i)%r
          camel(i)%sortObj = camel(i)%L-camel(i)%r
        end do
        
        camel(n:1:-1) = qsort(camel(1:n))
        
        
        seat(1:n) = .false.
        ans = 0
        do i = 1,n
          if( camel(i)%sortObj<=0 )then
            ii = i
            goto 100
          end if
          
          if( .not.(seat(camel(i)%k)) )then
            ans = ans + camel(i)%l
            seat(camel(i)%k) = .true.
          else
            ans = ans + camel(i)%r
          end if
        end do
        
        
        anss(c) = ans
        
        cycle
    100 continue
        
        do i = ii,n
          ans = ans + camel(i)%r
        end do
        anss(c) = ans
        
        
      end do
      
      
      do i = 1,t
        print'(i0)',anss(i)
      end do
      
      
      stop
      !debugg
      
      print*,' '
      do i = 1,n
        print'(*(i0,x))',camel(i)%k,camel(i)%l,camel(i)%r,camel(i)%sortObj
      end do
      
      END PROGRAM