// They Plan, and Allah Plans...
// Indeed Allah is the Best of Planners.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*======================================= Macro Start====================================================*/
#define fastio \
ios_base::sync_with_stdio(false); \
cin.tie(NULL);
#define precise \
cout.precision(10); \
cout << fixed;
#define all(x) x.begin(), x.end()
#define endl "\n"
#define memset(arr, init) memset(arr, init, sizeof(arr))
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * (b / gcd(a, b)))
#define bitoggle(number, pos) number ^ (1 << pos)
#define checkbit(number, pos) number &(1 << pos)
#define biton(number, pos) number | (1 << pos)
const double PI = acos(-1);
const ll infinity = (1000000000 + 7);
void solve()
{
int d;
cin >> d;
int n;
cin >> n;
int grid[1025][1025], sgx[1025][1025], sgy[1025][1025];
memset(grid, 0);
memset(sgx, 0);
memset(sgy, 0);
for (int i = 0; i < n; i++)
{
int x, y, popu;
cin >> x >> y >> popu;
grid[x][y] = popu;
}
int ans = 0;
for (int i = 0; i < 1025; i++)
{
for (int j = 0; j < 1025; j++)
{
sgx[i][j] = grid[i][j];
sgy[i][j] = grid[i][j];
if (i != 0)
{
sgx[i][j] += sgx[i - 1][j];
}
if (j != 0)
{
sgy[i][j] += sgy[i][j - 1];
}
int a = sgx[i][j], b = sgy[i][j];
if ((i - 2 * d) > 0)
{
a -= sgx[i - 2 * d - 1][j];
}
if ((j - 2 * d) > 0)
{
b -= sgy[i][j - 2 * d - 1];
}
ans = max(ans, a + b);
}
}
cout << ans << endl;
}
void Task()
{
int test;
cin >> test;
for (int i = 1; i <= test; i++)
{
//cout << "Case " << i << ": ";
solve();
}
}
int main()
{
Task();
return 0;
}
Ly8gVGhleSBQbGFuLCBhbmQgQWxsYWggUGxhbnMuLi4KLy8gSW5kZWVkIEFsbGFoIGlzIHRoZSBCZXN0IG9mIFBsYW5uZXJzLgoKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwovKj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PSBNYWNybyBTdGFydD09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0qLwojZGVmaW5lIGZhc3RpbyAgICAgICAgICAgICAgICAgICAgICAgIFwKCWlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOyBcCgljaW4udGllKE5VTEwpOwojZGVmaW5lIHByZWNpc2UgICAgICAgICBcCgljb3V0LnByZWNpc2lvbigxMCk7IFwKCWNvdXQgPDwgZml4ZWQ7CiNkZWZpbmUgYWxsKHgpIHguYmVnaW4oKSwgeC5lbmQoKQojZGVmaW5lIGVuZGwgIlxuIgojZGVmaW5lIG1lbXNldChhcnIsIGluaXQpIG1lbXNldChhcnIsIGluaXQsIHNpemVvZihhcnIpKQojZGVmaW5lIGdjZChhLCBiKSBfX2djZChhLCBiKQojZGVmaW5lIGxjbShhLCBiKSAoYSAqIChiIC8gZ2NkKGEsIGIpKSkKI2RlZmluZSBiaXRvZ2dsZShudW1iZXIsIHBvcykgbnVtYmVyIF4gKDEgPDwgcG9zKQojZGVmaW5lIGNoZWNrYml0KG51bWJlciwgcG9zKSBudW1iZXIgJigxIDw8IHBvcykKI2RlZmluZSBiaXRvbihudW1iZXIsIHBvcykgbnVtYmVyIHwgKDEgPDwgcG9zKQoKY29uc3QgZG91YmxlIFBJID0gYWNvcygtMSk7CmNvbnN0IGxsIGluZmluaXR5ID0gKDEwMDAwMDAwMDAgKyA3KTsKCnZvaWQgc29sdmUoKQp7CglpbnQgZDsKCWNpbiA+PiBkOwoJaW50IG47CgljaW4gPj4gbjsKCWludCBncmlkWzEwMjVdWzEwMjVdLCBzZ3hbMTAyNV1bMTAyNV0sIHNneVsxMDI1XVsxMDI1XTsKCW1lbXNldChncmlkLCAwKTsKCW1lbXNldChzZ3gsIDApOwoJbWVtc2V0KHNneSwgMCk7Cglmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKCXsKCQlpbnQgeCwgeSwgcG9wdTsKCQljaW4gPj4geCA+PiB5ID4+IHBvcHU7CgkJZ3JpZFt4XVt5XSA9IHBvcHU7Cgl9CglpbnQgYW5zID0gMDsKCWZvciAoaW50IGkgPSAwOyBpIDwgMTAyNTsgaSsrKQoJewoJCWZvciAoaW50IGogPSAwOyBqIDwgMTAyNTsgaisrKQoJCXsKCQkJc2d4W2ldW2pdID0gZ3JpZFtpXVtqXTsKCQkJc2d5W2ldW2pdID0gZ3JpZFtpXVtqXTsKCQkJaWYgKGkgIT0gMCkKCQkJewoJCQkJc2d4W2ldW2pdICs9IHNneFtpIC0gMV1bal07CgkJCX0KCQkJaWYgKGogIT0gMCkKCQkJewoJCQkJc2d5W2ldW2pdICs9IHNneVtpXVtqIC0gMV07CgkJCX0KCgkJCWludCBhID0gc2d4W2ldW2pdLCBiID0gc2d5W2ldW2pdOwoJCQlpZiAoKGkgLSAyICogZCkgPiAwKQoJCQl7CgkJCQlhIC09IHNneFtpIC0gMiAqIGQgLSAxXVtqXTsKCQkJfQoJCQlpZiAoKGogLSAyICogZCkgPiAwKQoJCQl7CgkJCQliIC09IHNneVtpXVtqIC0gMiAqIGQgLSAxXTsKCQkJfQoJCQlhbnMgPSBtYXgoYW5zLCBhICsgYik7CgkJfQoJfQoJY291dCA8PCBhbnMgPDwgZW5kbDsKfQp2b2lkIFRhc2soKQp7CglpbnQgdGVzdDsKCWNpbiA+PiB0ZXN0OwoJZm9yIChpbnQgaSA9IDE7IGkgPD0gdGVzdDsgaSsrKQoJewoJCS8vY291dCA8PCAiQ2FzZSAiIDw8IGkgPDwgIjogIjsKCQlzb2x2ZSgpOwoJfQp9CgppbnQgbWFpbigpCnsKCVRhc2soKTsKCXJldHVybiAwOwp9