#include<bits/stdc++.h> 
using namespace std;
long long n,m,a[200010],b[200010],c[200010],sum,mx1,mx2,num[200010],k;
struct kkk
{
	long long id,nxt;
	friend bool operator<(kkk a,kkk b)
	{
		return a.nxt>b.nxt;
	}
};

struct an
{
	long long id,nm;
}num2[200010];
long long js(long long i,long long k)
{
	return a[i]*k*k+b[i]*k+c[i];
}
priority_queue<kkk>Q;
bool cnp(an x,an y)
{
	return x.nm>y.nm;
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	m=k<<1;
	m-=n;
	for(long long i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
		num[i]=1;
		sum+=a[i]+b[i]+c[i];
		Q.push({i,js(i,2)});
	}
//	cout<<js(1,1)+js(1,2)+js(1,3)+js(2,1)+js(2,2)+js(3,1)+js(3,2)+js(4,1);
	while(m--)
	{
		kkk x=Q.top();
		Q.pop();
		if(num[x.id]==k)x=Q.top(),Q.pop();
		sum+=x.nxt;
		num[x.id]++;
		Q.push({x.id,js(x.id,num[x.id]+1)});
	}
	for(long long i=1;i<=n;i++)num2[i].nm=num[i],num2[i].id=i;
	sort(num2+1,num2+n+1,cnp);
	printf("%lld\n",sum);
	int l=1,r=n;
	while(l<r)
	{
		while(1)
		{
			while(num2[r].nm)
			{
				if(num2[l].nm==1)break;
				printf("%lld %lld\n",num2[l].id,num2[r].id);
				num2[l].nm--,num2[r].nm--;
			}
			if(!num2[r].nm) r--;
			if(num2[l].nm==1)
			{
				printf("%lld %lld\n",num2[l].id,num2[l+1].id);
				num2[++l].nm--;
			}
			if(l>=r)break;
		}
	}
//	4 3
//1 2 3
//2 3 4
//3 4 5
//4 5 6
	return 0;
}