//Arborele Partial de Cost Minim (Minimum spanning tree).
//Algoritmul Prim.
//Implementare in m*log(n) utilizind reprezentarea multimilor disjuncte.
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

struct muchie{
	int y,cost;
};

vector <muchie> L[200000], K;

int n,m;
int R[200000]; //Tatal fiecarui Element. Initial R[i]=0, i=1..n;
int H[200000]; //Adincimea fiecarui arbore partia. Initial H[i]=0, i=0..n;

ifstream inFile("apm.in");
ofstream outFile("apm.out");

int GetRoot(int x)
{
	while(R[x]){ x=R[x]; }
	return x;
}

void Read()  
{
	//Citim Graful
	//n - Numarul de noduri, variabila globala;
	//m - Numarul de Arce Neorinetate, variabila globala;
	//M - Lista Muchiilor
	inFile >> n >> m;
	int x, y, cost;
	for(int i=1; i<=m; i++){
		inFile >> x >> y >> cost;
		muchie m;
		m.y=y; m.cost=cost;
		L[x].push_back(m);
		m.y=x;
		L[y].push_back(m);
	}
}

int main()
{
	Read();

	int x, y, cost=0;
	int rx,ry;
	int index=1,ct;
	for(ct=1;ct<n;ct++){
		int i=index;
		int aux=1001;
		index=-1;
		rx=GetRoot(i);
		for(unsigned int j=0;j<L[i].size();j++){
			ry=GetRoot(L[i][j].y);
			if(rx!=ry && L[i][j].cost<aux){index=j; aux=L[i][j].cost;}
		}

		ry=GetRoot(L[i][index].y);
			K.push_back(L[i][index]);
			cost+=L[i][index].cost;
			if(rx>ry){ R[ry]=rx; }
			if(rx<ry){ R[rx]=ry; }
			if(rx==ry){ R[rx]=ry; H[ry]++; }
	}

	outFile << cost << "\n" << n-1 << "\n";
	for(int i=1;i<=ct;i++){
		outFile << i << " " << K[i].y << "\n";
	}
	
}