using namespace std;
#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
#define pq priority_queue
#define mp make_pair
#define pi pair<pair<int,int>, pair<int,int> >
#define NMAX 200000
#define MMAX 400000
#define InFile "apm.in"
#define OutFile "apm.out"
#define nod1 first.first
#define nod2 first.second
#define cost second.first
#define ord second.second
struct Qcomp
{
	bool operator()(const pi &a,const pi &b) const
	{
		return a.cost>b.cost;
	}
};
int v[NMAX],chosen[MMAX];
int main ()
{
	vector <pi> m(MMAX);
	int k=0;
	long apm_cost=0;
	pq<pi,vector<pi>,Qcomp> heap;
	int n,nrm,i;
	ifstream f(InFile);
	f>>n>>nrm;
	for(i=1;i<=nrm;i++)
	{
		f>>m[i].nod1>>m[i].nod2>>m[i].cost;
		m[i].ord=i;
		heap.push(m[i]);
	}
	ofstream g(OutFile);
	while(!heap.empty())
	{
		pi x;
		x=heap.top();
		heap.pop();
		if(!v[x.nod1] && !v[x.nod2])
		{
			k++;
			chosen[x.ord]=1;
			v[x.nod1]=v[x.nod2]=k;
			apm_cost+=x.cost;
		}
		else
			if(x.nod1&&!v[x.nod2])
			{
				chosen[x.ord]=1;
				v[x.nod2]=v[x.nod1];
				apm_cost+=x.cost;
			}
			else
				if(x.nod2&&!v[x.nod1])
				{
					chosen[x.ord]=1;
					v[x.nod1]=v[x.nod2];
					apm_cost+=x.cost;
				}
				else
					if(v[x.nod1]!=v[x.nod2]&&v[x.nod1]&&v[x.nod2])
					{
						chosen[x.ord]=1;
						apm_cost+=x.cost;
						int aux=min(v[x.nod1],v[x.nod2]),cut_comp=max(v[x.nod1],v[x.nod2]);
						for(i=1;i<=n;i++)
							if(v[i]==cut_comp)
								v[i]=aux;
					}
	}
	g<<apm_cost<<"\n"<<n-1<<"\n";
	for(i=1;i<=nrm;i++)
		if(chosen[i]) g<<m[i].nod1<<" "<<m[i].nod2<<"\n";
	f.close();
	g.close();
	return 0;
}