#include<iostream>
#include<algorithm>
#include<fstream>
using namespace std;

const int N=100005;

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

int T[N], n, m, nr;
Muchie edge[N], sol[N];

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

bool comp(Muchie a, Muchie b){
	return a.c<b.c;
}

int tata(int x){
	if (x == T[x])
		return x;
	return T[x]=tata(T[x]);
}

void merge(int x, int y){
	x=tata(x);
	y=tata(y);
	
	if (x != y)
		T[y] = x;
}

void kruskal(){
	sort(edge+1, edge+m+1,comp);
	
	int C = 0;
	
	for(int i=1;i<=n;i++)
		T[i]=i;
	
	for (int i=1;i<=m;i++)
		if(tata(edge[i].x)!=tata(edge[i].y)){
			merge(edge[i].x,edge[i].y);
			sol[++nr]=edge[i];
			C+=edge[i].c;
		}
	
	out<<C<<"\n"<<nr<<"\n";
	for (int i=1;i<=nr;i++)
		out<<sol[i].x<<" "<<sol[i].y<<"\n";
}

int main(){
	in>>n>>m;
	
	for (int i=1;i<=m;i++)
		in>>edge[i].x>>edge[i].y>>edge[i].c;
	
	kruskal();
	
	return 0;
}