#include <iostream>#include <stdio.h>#include <string.h>#include <math.h>using namespace std;#define LL long longconst int maxn=100005;struct node{ int x,y; int w;};node p[maxn];int q[maxn];LL d[maxn],w[maxn],f[maxn];int c,n,t;int abs(int x){ return x<0?(-x):x;}LL dis(int a,int b){ return abs(p[a].x-p[b].x)+abs(p[a].y-p[b].y);}void dp(){ int head=0,tail=0,i; q[tail++]=0; f[0]=0; for (i=1;i<=n;i++) { while (head<tail && w[i]-w[q[head]]>c) head++; int j=q[head]; f[i]=f[j]+dis(0,j+1)+d[i]-d[j+1]+dis(i,0); while (head<tail) { int j=q[tail-1]; if (f[j]+dis(0,j+1)-d[j+1] < f[i]+dis(0,i+1)-d[i+1]) break; tail--; } q[tail++]=i; } printf("%lldn",f[n]);}int main(){ int i; scanf("%d",&t); while (t--) { scanf("%d",&c); scanf("%d",&n); for (i=1;i<=n;i++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].w); p[0].x=0; p[0].y=0; d[0]=0; w[0]=0; for (i=1;i<=n;i++) { d[i]=d[i-1]+dis(i-1,i); w[i]=w[i-1]+(LL)p[i].w; } dp(); } return 0;}
