Problem Description

Calabash is now playing an RPG game on his computer. In this game, there are $n$ unknown numbers $x_1,x_2,\dots,x_n$ and $m$ NPCs selling hints. The $i$-th NPC is selling $c_i$ hints. Each hint contains three integers $l_j,r_j,w_j$, which means Calabash can pay $w_j$ coins to buy this hint, and this hint can tell Calabash the value of $x_{l_j}+x_{l_j+1}+\dots+x_{r_j-1}+x_{r_j}$.

The target of the game is to figure out all the $n$ unknown numbers. Clever Calabash knows how to buy hints optimally, but NPCs are greedy, for the $i$-th NPC, Calabash must buy exactly $k_i$ hints from him. Note that each hint can't be bought more than once.

This problem is much more difficult for Calabash. Please write a program to help Calabash find the cheapest way, or determine it is impossible.

Input

The first line of the input contains an integer $T(1\leq T\leq 10)$, denoting the number of test cases.

In each test case, there are two integers $n,m(1\leq n,m\leq 80)$ in the first line, denoting the number of unknown numbers and NPCs.

For the next $m$ parts, there are two integers $c_i,k_i(1\leq k_i\leq c_i)$ in the first line, denoting the number of hints the $i$-th NPC has and the limit for the $i$-th NPC.

For the next $c_i$ lines, each line contains three integers $l_j,r_j,w_j(1\leq l_j\leq r_j\leq n,1\leq w_j\leq 10^6)$, describing each hint offered by the $i$-th NPC.

It is guaranteed that $\sum c_i\leq 80$ in each test case.

Output

For each test case, print a single line containing an integer, denoting the minimum number of coins. If there is no solution, output ``$\texttt{-1}$'' instead.

2
2 2
1 1
1 2 1
3 2
1 1 10
2 2 100
1 2 1000
2 2
1 1
1 1 1
1 1
1 1 2

111
-1