#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 500005;
const int team = 6;
struct Player {
ll k;
int dur, id;
void olvas(int i) {
id = i;
cin>>k>>dur;
}
const bool operator< (Player masik) const {
return k > masik.k;
}
};
Player tab[maxn];
int fin[maxn * team];
int n, m;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>m>>n;
for(int i=0;i<n;i++) {
tab[i].olvas(i);
}
sort(tab,tab+n);
int it = 0;
int ben = 0;
ll summa = 0LL;
for(int i=0;i<team*m;i++) {
fin[i] = tab[it].id;
summa += tab[it].k;
ben++;
if(ben == tab[it].dur) {
ben = 0;
it++;
}
}
cout<<summa<<endl;
for(int i=0;i<team;i++) {
cout<<fin[ i*m ]+1<<" ";
}
cout<<endl;
int db = 0;
for(int j=1;j<m;j++) {
for(int i=0;i<team;i++) {
if(fin[i*m + j - 1] != fin[i*m + j]) db++;
}
}
cout<<db<<endl;
for(int j=1;j<m;j++) {
for(int i=0;i<team;i++) {
if(fin[i*m + j - 1] != fin[i*m + j]) {
cout<<j<<" "<<fin[i*m + j - 1] + 1<<" "<<fin[i*m + j] + 1<<endl;
}
}
}
return 0;
}
