#include <fstream>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct  Muchie
{
	int x,y,cost;
};


int N, M;
vector<Muchie>L,APM;
vector<int> repr;
vector<int> h;

bool cmp(Muchie a, Muchie b)
{
	return a.cost < b.cost;
}

int find1(int x)
{
	while(repr[x])
	{
		x = repr[x];
	}
	return x;
}
void union1(int x,int y)
{
    int A=find1(x);
    int B=find1(y);
    if(A!=B)
    {
    if(h[A]>h[B])
    {
        repr[B]=A;
        return;
    }
    if(h[B]>h[A])
    {
        repr[A]=B;
        return;
    }
    repr[B]=A;
    h[A]++;
    }

}

int main()
{
	f >> N >> M;
	L.resize(M+1);
	APM.resize(N);
	repr.resize(N+1);
	h.resize(N+1);
	for ( int i = 0; i < M; i++ )
	{
		int x, y, cost;
		f >> x >> y >> cost;
		Muchie a;
		a.x = x;
		a.y = y;
		a.cost = cost;
		L[i] = a;
	}
	sort(L.begin(),L.end(),cmp);

	int nrsel = 0;
	int costTot = 0;

	for ( int i = 0; i < M && nrsel < N-1; i++ )
	{
		int x = L[i].x;
		int y = L[i].y;
		int cost = L[i].cost;
		if ( find1(x) != find1(y) )
		{
			costTot += cost; 
			APM[nrsel++] = L[i];
			union1(x,y);
		}
	}
	g << costTot << "\n" ;
	g << N-1 << "\n";
	for ( int i = 0; i < nrsel; i++ )
	{
		g << APM[i].x << " " << APM[i].y << "\n" ;
	}

	return 0;
}