#include <iostream>
#include <algorithm>
#define FIN "apm.in"
#define FOUT "apm.out"
#define MAX_N 200010
#define MAX_M 400010
#define F first
#define S second
using namespace std;
int M,N;
pair< int , pair< int , int > > v[MAX_M];
int rank[MAX_N];
int P[MAX_N];
int ctotal;
pair< int , int > sol [MAX_N];
int csol=0;

int find_set(int x){

	if (x!=P[x]){ P[x]=find_set(P[x]);}
	return P[x];
};

void merge_sets(int x,int y,int cost) {
	int sx=find_set(x);
	int sy=find_set(y);
	if (sx!=sy){
		ctotal+=cost;
		++csol;
		sol[csol].F=x;
		sol[csol].S=y;
		if (rank[sx]<rank[sy]){P[sx]=sy;} else {P[sy]=sx;}
		if (rank[sx]==rank[sy]){++rank[sx];}
	}
}

int main(void){

	freopen(FIN,"rt",stdin);
	freopen(FOUT,"wt",stdout);
	ctotal=0;

	scanf("%d%d",&N,&M);
	for (int i=1;i<=N;++i){P[i]=i;rank[i]=0;}

	for (int i=1;i<=M;++i) scanf("%d%d%d",&v[i].S.F,&v[i].S.S,&v[i].F);
	sort(v+1,v+M+1);

	for (int i=1;i<=M;++i) merge_sets(v[i].S.F,v[i].S.S,v[i].F);

	printf("%d\n",ctotal);
	printf("%d\n",csol);
	for (int i=1;i<=csol;++i) printf("%d %d\n",sol[i].F,sol[i].S);

	fclose(stdin);
	fclose(stdout);
	return 0;
}