#include<iostream>
using namespace std;
typedef struct node
{
int price;
int wei;
}Node;
Node a[3000];
int dp[3000][3000];
int main()
{
int text;
cin>>text;
while(text--)
{
int n,m;
cin>>n>>m;
int num;
int i,j;
int k = 1;
for(i = 0;i < m;i++)
{
cin>>a[k].price;
cin>>a[k].wei;
cin>>num;
k++;
for(j = 1;j < num;j++ )
{
a[k].price = a[k-1].price;
a[k].wei = a[k-1].wei;
k++;
}
}
for(j = 0;j < a[1].price;j++)
dp[1][j] = 0;
for(j = a[1].price;j <= n;j++)
dp[1][j] = a[1].wei;
for(i = 2;i < k;i++ )
{
for(j = 0;j <= n;j++)
{
if(a[i].price > j)
dp[i][j] = dp[i-1][j];
else
{
if(dp[i-1][j] > dp[i-1][j-a[i].price]+a[i].wei)
dp[i][j] = dp[i-1][j];
else
dp[i][j] = dp[i-1][j-a[i].price]+a[i].wei;
}
}
}
cout<<dp[k-1][n]<<endl;
}
return 0;
}