#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <ctime>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream ff("apm.in");
ofstream gg("apm.out");
#define max 200001

struct edg{ int a,b,c; }mm[2*max];
int n, m, rr[max];

bool cmp(edg a, edg b){ return a.c<b.c; }

int rad(int a){
	if(rr[a]==a) return a; else{
		rr[a]=rad(rr[a]);
		return rr[a];
	}
}

void apm(){
	int s=0, k=0;
	for(int i=1;i<=n;i++) rr[i]=i;
	for(int i=1;i<n;i++){
		while(k<m && rad(mm[k].a)==rad(mm[k].b))k++;
		if(rad(mm[k].a)!=rad(mm[k].b)){
			s+=mm[k].c;
			mm[k].c=1001;
			rr[rad(mm[k].a)]=rad(mm[k].b);
		}
		k++;
	}
	gg << s << "\n";
	gg << n-1 << "\n";
	for(int i=0;i<m;i++)
	if(mm[i].c==1001) gg << mm[i].a << " " << mm[i].b << "\n";
}

int main(){
	ff >> n >> m;
	for(int i=0;i<m;i++) ff >> mm[i].a >> mm[i].b >> mm[i].c;
	sort(mm, mm+m, cmp);
	apm();
	return 0;
}