#include <fstream>
using namespace std;

#define maxn 200001

typedef struct muchie{
	int x,y,cost;};

int t[maxn],n,m,nh;
muchie b[maxn],sol[maxn];

void swap(int x,int y){
	int aux;
	aux=b[x].x;
	b[x].x=b[y].x;
	b[y].x=aux;
	aux=b[x].y;
	b[x].y=b[y].y;
	b[y].y=aux;
	aux=b[x].cost;
	b[x].cost=b[y].cost;
	b[y].cost=aux;}

void sift(int k){
	int son;
	do{
		son=0;
		if(k*2<=nh)
			son=k*2;
		if(k*2+1<=nh&&b[k*2].cost>b[k*2+1].cost)
			son=k*2+1;
		if(b[son].cost>b[k].cost)
			son=0;
		if(son){
			swap(son,k);
			k=son;}}
	while(son);}

void push(int k){
	while(k/2&&b[k].cost<b[k/2].cost){
		swap(k,k/2);
		k=k/2;}}

void pop(){
	swap(1,nh);
	nh--;
	sift(1);}

int root(int k){
	while(t[k])
		k=t[k];
	return k;}

int main(){
	ifstream f("apm.in");
	ofstream g("apm.out");
	f>>n>>m;
	int i,c=0,nr=0;
	muchie u;
	while(nh<=m){
		f>>u.x>>u.y>>u.cost;
		nh++;
		b[nh]=u;
		push(nh);}
	while(nh){
		muchie min;
		min=b[1];
		pop();
		if(root(min.x)!=root(min.y)){
			t[root(min.y)]=root(min.x);
			c=c+min.cost;
			nr++;
			sol[nr]=min;}}
	g<<c<<"\n"<<nr<<"\n";
	for(i=1;i<=nr;i++)
		g<<sol[i].x<<" "<<sol[i].y<<"\n";
	f.close();
	g.close();
	return 0;}