#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}
#define re return
mt19937 rnd(chrono::system_clock().now().time_since_epoch().count());
int rint(int v) {re rnd() % v;}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int m, n;
cin >> m >> n;
int I[n], K[n];
for(int i = 0; i < n; ++i)
cin >> K[i] >> I[i];
int f[m][6];
int p[n];
for(int i = 0; i < n; ++i) p[i] = i;
sort(p, p + n, [&] (const int &a, const int &b) {return K[a] > K[b];});
ll ans = 0;
int x = -1, y = 0;
for(int pt = 0; pt < n; ++pt) {
int i = p[pt];
for(int it = I[i]; it--; ) {
if(++x == m) ++y, x = 0;
if(y == 6) goto final;
f[x][y] = i + 1;
ans += K[i];
}
}
final:;
cout << ans << endl;
for(int i = 0; i < 6; ++i) cout << f[0][i] << ' ';
cout << endl;
vector< tuple<int, int, int> > v;
for(int i = 1; i < m; ++i) for(int j = 0; j < 6; ++j)
if(f[i][j] != f[i - 1][j]) v.emplace_back(i, f[i - 1][j], f[i][j]);
cout << v.size() << endl;
for(auto c : v) {
int x, a, b;
tie(x, a, b) = c;
cout << x << ' ' << a << ' ' << b << '\n';
}
}
