#include <cstring> #include<cstdio> #include<algorithm> #include <cstdlib> #include <iostream> using namespace std; const int maxn = 110000; int total[maxn],disto[maxn],w[maxn],C,n,x[maxn],y[maxn],d[maxn]; int q[maxn]; int func(int j){ return d[j] - total[j+1] + disto[j+1]; } int main() { int T,kase; scanf("%d",&T); while(T--){ if(kase++) printf("\n"); scanf("%d %d",&C,&n); w[0]=total[0]=disto[0]=x[0]=y[0]=0; for(int i=1;i<=n;i++){ int c; scanf("%d %d %d",&x[i],&y[i],&c); total[i]=total[i-1]+abs(x[i]-x[i-1])+abs(y[i]-y[i-1]); disto[i]=abs(x[i])+abs(y[i]); w[i]=w[i-1]+c; } q[1]=0; int front_,rear; front_=rear=1; for(int i=1;i<=n;i++){ while(front_<=rear && w[i] - w[q[front_]] > C) front_++; d[i]=func(q[front_]) + total[i] + disto[i]; while(front_<=rear && func(q[rear]) >= func(i) ) rear--; q[++rear]=i; } printf("%d\n",d[n]); } return 0; }