#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
const int MAX_TIME = 5e5 + 5;
int matrix[MAX_TIME][6], last[6];
int main() {
int M, N; cin >> M >> N;
vector<pii> v(N);
vector<int> life(N);
for (int i = 0; i < N; i++) {
cin >> v[i].first >> life[i];
v[i].second = i + 1;
}
sort(v.begin(), v.end());
vvi ans;
ll total = 0;
int cur_cell = 0, time_left = 0, power, id;
while (last[5] < M) {
if (time_left == 0) {
power = v.back().first;
id = v.back().second;
time_left = life[id - 1];
v.pop_back();
}
while (time_left > 0) {
if (last[5] == M) break;
matrix[last[cur_cell]][cur_cell] = id;
last[cur_cell]++;
total += power;
time_left--;
if (last[cur_cell] == M && cur_cell != 5) {
cur_cell++;
break;
}
}
}
cout << total << '\n';
cout << matrix[0][0] << ' ' << matrix[0][1] << ' ' << matrix[0][2] << ' ';
cout << matrix[0][3] << ' ' << matrix[0][4] << ' ' << matrix[0][5] << '\n';
for (int cell = 0; cell < 6; cell++) {
for (int time = 1; time < M; time++) {
if (matrix[time][cell] != matrix[time - 1][cell]) {
ans.push_back({ time, matrix[time - 1][cell], matrix[time][cell] });
}
}
}
sort(ans.begin(), ans.end());
for (auto i : ans) {
cout << i[0] << ' ' << i[1] << ' ' << i[2] << '\n';
}
return 0;
}
