밀크 캔디

Calabash는 컴퓨터로 RPG 게임을 하고 있습니다. 값을 모르는 수 $n$개 $x_1, x_2, \ldots, x_n$과 힌트를 파는 NPC $m$명이 있습니다. $i$번째 NPC는 힌트 $c_i$개를 팝니다. 각 힌트에는 정수 $l_j$, $r_j$, $w_j$가 있습니다. $w_j$ 코인을 내고 이 힌트를 사면 $x_{l_j} + x_{l_j+1} + \cdots + x_{r_j}$의 값을 알 수 있습니다.

목표는 $n$개의 수를 모두 알아내는 것입니다. Calabash는 힌트를 최적으로 고르지만, NPC는 욕심이 많습니다. Calabash는 $i$번째 NPC에게서 정확히 $k_i$개의 힌트를 사야 합니다. 같은 힌트는 두 번 살 수 없습니다.

모든 수를 알아내기 위해 Calabash가 내야 하는 코인의 최솟값을 구하세요. 불가능하면 그 사실을 판단하세요.

첫 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10$)가 주어집니다.

각 테스트 케이스는 $n$과 $m$ ($1 \le n, m \le 80$)으로 시작합니다. 이후 NPC마다 $c_i$와 $k_i$ ($1 \le k_i \le c_i$)가 적힌 줄이 있고, 이어서 $c_i$개의 줄에 $l_j$, $r_j$, $w_j$ ($1 \le l_j \le r_j \le n$, $1 \le w_j \le 10^6$)가 주어집니다.

한 테스트 케이스에서 모든 $c_i$의 합은 80 이하입니다.

각 테스트 케이스마다 최소 코인 수를 한 줄에 출력하세요. 해가 없으면 $-1$을 출력하세요.