#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<queue>
#include<ctime>
#include<cassert>
#include<complex>
#include<string>
#include<cstring>
#include<chrono>
#include<random>
#include<bitset>
#include<iomanip>
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define sz(v) (int) v.size()
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int MAX_N = 5e5 + 5;
int m, n;
pii a[MAX_N];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> m >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i].fi >> a[i].se;
}
vector<int> order(n);
iota(all(order), 1);
sort(all(order), [&](int i, int j) {
return a[i] > a[j];
});
vector<vector<int>> go(6);
vector<int> sum(6);
ll ans = 0;
vector<pair<int, pii>> subst;
for (int i : order) {
bool found = true;
while (a[i].se && found) {
found = false;
pii curr = mp(0, -1);
for (int j = 0; j < 6; ++j) {
if (sum[j] < m) {
curr = max(curr, mp(sum[j], j));
}
}
if (curr.se != -1) {
if (!go[curr.se].empty()) {
subst.eb(sum[curr.se], mp(go[curr.se].back(), i));
}
go[curr.se].eb(i);
int play = min(m - sum[curr.se], a[i].se);
ans += 1ll * a[i].fi * play;
sum[curr.se] += play;
a[i].se -= play;
found = true;
}
}
}
cout << ans << "\n";
for (int i = 0; i < 6; ++i) {
cout << go[i][0] << " ";
}
cout << "\n" << sz(subst) << "\n";
for (auto &pp : subst) {
cout << pp.fi << " " << pp.se.fi << " " << pp.se.se << "\n";
}
return 0;
}
