#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int n,m,ct=0;
int tata[300005], grad[300005];

vector<pair<int, int> > Graf;

priority_queue <pair <int, pair <int, int> > > Heap;

void Read(){
	FILE *f = fopen("apm.in","r");
	int aux1, aux2, cost;
	fscanf(f,"%d %d",&n,&m);

	for(int i=1;i<=n;i++){
		tata[i] = i;
		grad[i] = 1;
	}

	for(int i=0;i<m;i++){
		fscanf(f,"%d %d %d",&aux1, &aux2, &cost);
		Heap.push(make_pair(-cost, make_pair(aux1, aux2)));
		Heap.push(make_pair(-cost, make_pair(aux2, aux1)));
	}
}

void unite(int node1, int node2){
	if(grad[node1] > grad[node2]){
		tata[node2] = tata[node1];
		grad[node1] += grad[node2];
	}
	else{
		tata[node1] = tata[node2];
		grad[node2] += grad[node1];
	}
}

int find_father(int node){
	if(tata[node] == node)
		return node;

	int rasp = find_father(tata[node]);
	tata[node] = rasp;
	return rasp;
}

void Kruskal(){
	while(!Heap.empty()){
		pair <int, pair <int, int> > best = Heap.top();
		Heap.pop();
		int nod1 = best.second.first;
		int nod2 = best.second.second;
		int cost = -best.first;

		if(find_father(nod1) != find_father(nod2)){
			Graf.push_back(make_pair(nod1, nod2));
			unite(find_father(nod1), find_father(nod2));
			ct += cost;
		}
	}
}

int main(){
	FILE *g = fopen("apm.out","w");
	Read();
	Kruskal();
	fprintf(g,"%d\n%d\n",ct,n-1);
    for(int i=0;i<n-1;i++)
    {
        fprintf(g,"%d %d\n", Graf[i].first, Graf[i].second);
    }
	return 0;
}