#include <bits/stdc++.h>
using namespace std;
#define int long long
const int S = 2005, N = 1e5 + 5;
int v[N], w[N], k[N], DP[12 * S][S];
vector<pair<int, int>> val[S];
signed main(){
int s, n; cin >> s >> n;
for (int i = 1; i <= n; i++){
cin >> v[i] >> w[i] >> k[i];
val[w[i]].push_back({v[i], k[i]});
}
vector<pair<int, int>> avl;
for (int i = 1; i <= s; i++){
sort(val[i].rbegin(), val[i].rend());
int C = 0;
for (auto &j : val[i]) C += j.second;
while (val[i].size() && C - val[i].back().second >= s / i){
C -= val[i].back().second;
val[i].pop_back();
}
if (val[i].size()){
val[i].back().second -= max(0ll, C - s / i);
}
for (auto &j : val[i]){
for (int K = 0; K < j.second; K++) avl.push_back({i, j.first});
}
}
n = avl.size();
int ans = 0;
for (int ii = 0; ii < n; ii++){
auto [W, V] = avl[ii];
cout << W << ' ' << V << endl;
int i = ii + 1;
for (int j = 0; j <= s; j++){
DP[i][j] = DP[i - 1][j];
if (j >= W)
DP[i][j] = max(DP[i][j], DP[i - 1][j - W] + V);
ans = max(ans, DP[i][j]);
}
}
cout << ans << endl;
}
