#include<fstream>
using namespace std;
int n,m,ns;
struct Muchie{int x,y,cost;};
Muchie G[400010];
int arbore[200010],c[200010];
char s[1000];

inline bool Ordonare(const Muchie A,const Muchie B)
{
	if(A.cost==B.cost)
	{
		if(A.x==B.x)
			return A.y<B.y;
		return A.x<B.x;
	}
	return A.cost<B.cost;
}

void Initializari()
{
	int i,j,x,y,z;
	bool minus;
	//parsez citirea
	ifstream fin("apm.in");
	fin.getline(s,999);
	ns=strlen(s);
	//pentru n
	n=s[0]-'0';
	i=1;
	while(s[i]>='0' && s[i]<='9')
	{
		n=n*10+(s[i]-'0');
		i++;
	}
	i++;
	//pentru m
	m=s[i]-'0';
	i++;
	while(s[i]>='0' && s[i]<='9' && i<ns)
	{
		m=m*10+(s[i]-'0');
		i++;
	}
	for(i=1;i<=m;i++)
	{
		fin.getline(s,999);
		ns=strlen(s);
		minus=false;
		//pentru G[i].x
		x=s[0]-'0';
		j=1;
		while(s[j]>='0' && s[j]<='9')
		{
			x=x*10+(s[j]-'0');
			j++;
		}
		j++;
		//pentru G[i].y
		y=s[j]-'0';
		j++;
		while(s[j]>='0' && s[j]<='9')
		{
			y=y*10+(s[j]-'0');
			j++;
		}
		j++;
		//pentru G[i].cost
		if(s[j]=='-')
		{
			j++;
			minus=true;
		}
		z=s[j]-'0';
		j++;
		while(s[j]>='0' && s[j]<='9' && j<ns)
		{
			z=z*10+(s[j]-'0');
			j++;
		}
		G[i].x=x;
		G[i].y=y;
		if(minus==true)
			G[i].cost=-z;
		else
			G[i].cost=z;
	}
	fin.close();
	for(i=1;i<=n;i++)
		c[i]=i;
}

void Kruskal()
{
	int i,j,minim,maxim,nr=0; //nr = numarul de muchii selectate
	for(i=1;nr<n-1;i++)
	{
		if(c[G[i].x]!=c[G[i].y]) //daca muchia nu ar forma cicluri cu cele deja selectate
		{
			arbore[++nr]=i; //selectez muchia i
			//unific cele doua componente conexe
			if(c[G[i].x]<c[G[i].y])
			{
				minim=c[G[i].x];
				maxim=c[G[i].y];
			}
			else
			{
				minim=c[G[i].y];
				maxim=c[G[i].x];
			}
			for(j=1;j<=n;j++)
				if(c[j]==maxim)
					c[j]=minim;
		}
	}
}

void AfisareArbore()
{
	ofstream fout("apm.out");
	int i,cost=0;
	for(i=1;i<n;i++)
	{
		cost+=G[arbore[i]].cost;
	}
	fout<<cost<<"\n"<<n-1<<"\n";
	for(i=1;i<n;i++)
	{
		fout<<G[arbore[i]].x<<' '<<G[arbore[i]].y<<"\n";
	}
	fout.close();
}

int main()
{
	Initializari();
	
	sort(G+1,G+m+1,Ordonare); //sortez muchiile crescator dupa cost
	
	Kruskal(); //determin arborele partial de cost minim
	//selectand n-1 muchii de cost minim,care nu formeaza cicluri
	
	AfisareArbore(); //afisez APM
	
	return 0;
}