#include <bits/stdc++.h>

 #define pii pair<int,int>

 #define INF 0x7f7f7f7f

 #define LL long long

 using namespace std;

 const int N=;

 LL dp[N];

 int n, m, w[N], a[N], b[N];

 LL cal()

 {

     memset(dp, , sizeof(dp));

     for(int i=; i<=n; i++)  //礼物

     {

         for(int j=m; j-w[i]>=; j--) //先来一次01背包

         {

             if( dp[j-w[i]]+ a[i] + b[i] > dp[j] )

                 dp[j]=dp[j-w[i]]+ a[i] + b[i]  ;

         }

         for(int j=; j+w[i]<=m; j++) //再来一次完全背包

         {

             if( dp[j+w[i]] < dp[j]+a[i] )

                 dp[ j+w[i] ] = dp[j]+a[i] ;

         }

     }

     LL sum=-;

     for(int i=m; i>; i--)    sum=max(sum, dp[i]);

     return sum;

 }

 int main()

 {

     freopen("input.txt", "r", stdin);

     int t;

     cin>>t;

     while(t--)

     {

         scanf("%d %d", &m, &n);

         for(int i=; i<=n; i++)    scanf("%d%d%d",&w[i], &a[i], &b[i]);

         printf("%lld\n", cal());

     }

     return ;

 }