Milk Candy

Calabash is playing an RPG on his computer. There are $n$ unknown numbers $x_1, x_2, \ldots, x_n$ and $m$ NPCs who sell hints. The $i$-th NPC sells $c_i$ hints. Each hint has three integers $l_j$, $r_j$, and $w_j$. Buying it costs $w_j$ coins and reveals the value of $x_{l_j} + x_{l_j+1} + \cdots + x_{r_j}$.

The goal is to determine all $n$ unknown numbers. Calabash buys hints optimally, but each NPC is greedy: Calabash must buy exactly $k_i$ hints from the $i$-th NPC. A single hint cannot be bought more than once.

Find the minimum number of coins Calabash must pay to determine all numbers, or determine that it is impossible.

The first line contains $T$ ($1 \le T \le 10$), the number of test cases.

Each test case starts with $n$ and $m$ ($1 \le n, m \le 80$). Then, for each NPC, there is a line with $c_i$ and $k_i$ ($1 \le k_i \le c_i$), followed by $c_i$ lines, each containing $l_j$, $r_j$, and $w_j$ ($1 \le l_j \le r_j \le n$, $1 \le w_j \le 10^6$).

The sum of all $c_i$ in a test case is at most 80.

For each test case, print the minimum number of coins on a single line. If there is no solution, print $-1$.