uva1169

#include <iostream>
#include <istream>
#include <sstream>
#include <vector>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <chrono>
#include <ctime>
#include <cmath>
#include <cctype>
#include <string>
#include <cstdio>
#include <iomanip>


#include <thread>
#include <mutex>
#include <condition_variable>
#include <functional>
#include <iterator>
using namespace std;
const int maxn = 100010;

int x[maxn] = {
     0 }, y[maxn] = {
    0}, z, n,c;
int dis[maxn] = {
     0 }, w[maxn] = {
     0 }, org[maxn] = {
     0 };
int q[maxn], d[maxn];

int fun(int i) {
    
	return d[i] - dis[i + 1] + org[i + 1];
}
int main()
{
    
	int t;
	cin >> t;
	while (t--) {
    
		cin >> c >> n;
		for (int i = 1; i <= n; i++) {
    
			cin >> x[i] >> y[i] >> z;
			org[i] = abs(x[i]) + abs(y[i]);
			w[i] = w[i - 1] + z;
			dis[i] = dis[i - 1] + abs(x[i] - x[i - 1]) + abs(y[i] - y[i - 1]);
		}
		int front = 1, rear = 1;
		for (int i = 1; i <= n; i++) {
    
			while (front <= rear && w[i] - w[q[front]] > c)++front;
			d[i] = fun(q[front]) + dis[i] + org[i];

			while (front <= rear && fun(i) <= fun(q[rear]))--rear;
			q[++rear] = i;
		}
		cout << d[n] << endl;
		if (t)cout << endl;
	}
	return 0;
}