#include<bits/stdc++.h>
using namespace std;
int n, m;
struct node {
	int mon, v, w, lans, lmon;
}a[101010];
bool cmp(node a, node b){
	if(a.v == b.v){
		if(a.mon == b.mon) return a.w < b.w;
		else return a.mon < b.mon; 
	}
	else return a.v > b.v;
}
int main() {
	long long sum = 0;
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		cin >> a[i].mon >> a[i].v >> a[i].w;
		if(a[i].w != 0) {
			a[i].lmon = a[a[i].w].mon;
			a[i].lans = a[a[i].w].mon * a[a[i].w].v;
		}
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++) {
		if(a[i].w != 0){
			if(a[i].mon + a[i].lmon < n){
				n -= a[i].mon + a[i].lmon;
				sum += a[i].mon * a[i].v + a[i].lmon * a[i].lans;
			}
		}
		else {
			if(a[i].mon < n) {
				n -= a[i].mon;
				sum += a[i].mon * a[i].v;
			}
		}
	}
	cout << sum << endl;
	return 0;
}