已经跑过样例和自测样例，没跑出问题。

思路是：总体贪心，先建树（类似Kruskal），再贪心地添加剩余边。

提交稽录

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
#define int long long
typedef long long ll;
struct node{
    ll a,b,c;
    int drg=0,id;
    node(int iid,ll aa,ll bb,ll cc){
    	id=iid,a=aa,b=bb,c=cc,drg=0;
	}
	node(){
	}
    ll calc()const{
        int d=drg+1;
        return a*d*d+b*d+c;
    }
    bool operator<(const node &o)const{
        return calc()>o.calc();
    }
}s[N];
int fa[N];
priority_queue<node> q;
int n,m;
void init(){
	for(int i=1;i<=n;i++) fa[i]=i;
}
int get(int x){
	return (fa[x]==x?x:fa[x]=get(fa[x]));
}
void merge(int x,int y){
	fa[get(x)]=get(y);
}
ll ans;
struct pans{
	int i,j;
	pans(int u,int v){
		i=u,j=v;
	}
};
vector<pans> p;
signed main(){
	cin>>n>>m;init();
	for(int i=1;i<=n;i++){
		ll a,b,c;cin>>a>>b>>c;
		q.push(node(i,a,b,c));
		s[i]=node(i,a,b,c);
	}
	for(int i=1;i<n;i++){
		node a=q.top();q.pop();
		node b=q.top();q.pop();
		if(get(a.id)==get(b.id)) continue;
		p.push_back(pans(a.id,b.id));
		merge(a.id,b.id);
		ans+=a.calc()+b.calc();
		s[a.id].drg++,s[b.id].drg++;
		a.drg++;b.drg++;
		q.push(a);q.push(b);
	}
	while(!q.empty()) q.pop();
	for(int i=1;i<=n;i++){
		q.push(s[i]);
	}
	for(int i=1;i<=m-(n-1);i++){
		node a=q.top();q.pop();
		node b=q.top();q.pop();
		p.push_back(pans(a.id,b.id));
		ans+=a.calc()+b.calc();
		a.drg++;b.drg++;
		q.push(a);q.push(b);
	}
	cout<<ans<<"\n";
	for(int i=0;i<p.size();i++){
		cout<<p[i].i<<" "<<p[i].j<<"\n";
	}
	return 0;
}