#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;

const int MX = 10000 + 5;
struct Seg {
    int l, r, h;
} S[MX];

LL sum;
int n, Rig;

LL get(int x) {
    LL ret = 0;
    for(int i = 1; i <= n; i++) {
        if(S[i].l < x) {
            ret += (LL)(min(S[i].r, x) - S[i].l) * S[i].h;
        }
    }
    return ret;
}

int solve() {
    int l = 0, r = Rig, m;
    while(l <= r) {
        m = (l + r) >> 1;
        LL left = get(m);
        if(left >= sum - left) r = m - 1;
        else l = m + 1;
    }

    LL ans = get(r + 1);

    l = 0, r = Rig;
    while(l <= r) {
        m = (l + r) >> 1;
        LL left = get(m);
        if(left > ans) r = m - 1;
        else l = m + 1;
    }
    return l - 1;
}

int main() {
    int T; //FIN;
    scanf("%d", &T);
    while(T--) {
        sum = 0;
        scanf("%d%d", &Rig, &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d%*d%d%d", &S[i].l, &S[i].r, &S[i].h);
            S[i].r += S[i].l;
            sum += (LL)(S[i].r - S[i].l) * S[i].h;
        }
        printf("%d\n", solve());
    }
    return 0;
}