프리미어 리그

Andrew와 Jordan은 열렬한 포켓몬 팬이고, 주변에도 포켓몬을 좋아하는 친구가 많다. 그런데 둘 다 승부욕이 대단하다. 이 승부욕을 풀어 줄 겸 작은 프리미어 드래프트 토너먼트인 프리미어 리그를 열려고 한다. Andy와 Jordan은 당신의 목록에 있는 각 포켓몬을 빌리겠다고 입찰했고, 빌린 포켓몬으로 연속된 대결을 치를 것이다. 대결이 공정하도록, 두 팬이 입찰하기 전에 대결 일정을 정해 두었다. 같은 트레이너가 소유한 두 포켓몬끼리의 대결은 어느 쪽이 이겨도 그 트레이너의 승리이므로 치르지 않는다.

토너먼트 주최자로서 당신은 누가 이기는지는 관심이 없다. 대신 이 토너먼트를 여는 데 드는 비용에는 관심이 있다. 다행히 대결을 치를 수 있는 체육관이 있지만, 체육관은 준비와 대결 후 회복을 위해 대결 요금을 받는다. 게다가 포켓몬을 하나하나 확보하는 데도 적지 않은 돈이 든다. Andy와 Jordan은 둘 다 포켓몬을 최대한 많이 원하지만, 포켓몬마다 지불할 의사가 있는 가격은 서로 다를 수 있다.

이제 입찰이 끝났으니, 각 포켓몬의 입찰에서 누가 이기는지 정해야 한다. 대결 일정, 각 포켓몬을 확보하는 데 드는 당신의 비용, 각 포켓몬에 대해 Andy와 Jordan이 지불할 의사가 있는 금액, 대결 비용이 주어질 때, 이 화려한 대결을 준비하는 데 드는 최소 총비용을 구하라. 모든 포켓몬은 Andy나 Jordan 중 한 명에게 배정되어야 한다.

첫째 줄에는 구매할 수 있는 포켓몬의 수 $1 \le n \le 10^2$가 주어진다. 다음 $n$개 줄에는 각각 $1 \le c\_i, a\_i, j\_i \le 10^5$이고 $a\_i, j\_i \le c\_i$인 정수 $3$개가 주어지는데, 차례대로 $i$번째 포켓몬을 확보하는 데 드는 당신의 비용, $i$번째 포켓몬에 대한 Andy의 입찰가, $i$번째 포켓몬에 대한 Jordan의 입찰가이다.

다음 줄에는 치를 대결의 수 $1 \le b \le 5 \cdot 10^2$가 주어진다. 그다음 $b$개 줄에는 각각 정수 $3$개 $1 \le a\_j, b\_j \le n$, $1 \le c\_j \le 10^5$가 주어지는데, $j$번째 대결이 포켓몬 $a\_j$와 $b\_j$ 사이에서 열리고 그 대결을 치르면 $c\_j$가 든다는 뜻이다. 같은 포켓몬 쌍 사이의 대결이 여러 번 주어질 수도 있다.

이 토너먼트를 운영하는 데 드는 최소 총비용을 한 수로 출력한다. 포켓몬이 비쌀 수 있지만, Andy와 Jordan의 입찰가로 비용을 상쇄할 수 있다.