#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

#define N 100007

int dp[N],T[N];

int dis[N],wt[N];

int que[N];

struct Point

{

    int x,y,w;

}p[N];

int f(int j)

{

    return dp[j]-T[j+]+dis[j+];

}

int DIS(int i,int j)

{

    return abs(p[i].x-p[j].x) + abs(p[i].y-p[j].y);

}

int main()

{

    int t,C,n,i,j;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&C);

        scanf("%d",&n);

        memset(que,,sizeof(que));

        wt[] = ;

        T[] = ;

        p[].x = p[].y = p[].w = ;

        for(i=;i<=n;i++)

        {

            scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].w);

            wt[i] = wt[i-] + p[i].w;

            T[i] = T[i-] + DIS(i,i-);

            dis[i] = DIS(i,);

        }

        int head = ;

        int tail = ;

        for(i=;i<=n;i++)

        {

            while(head <= tail && wt[i]-wt[que[head]] > C)

                head++;

            dp[i] = f(que[head]) + T[i] + dis[i];

            int fi = f(i);

            while(head <= tail && fi <= f(que[tail]))

                tail--;

            que[++tail] = i;

        }

        printf("%d\n",dp[n]);

        if(t)

            puts("");

    }

    return ;

}