#include <stdio.h>
#include <algorithm>
#include <vector>
#define MAX 200005
#define pii pair<int, int>
#define muc pair<int, pii>
#define mk make_pair
using namespace std;
  
int n, m, x, y, z, set[MAX], size[MAX], cost;
vector<muc> G;
vector<pii> arb;

int getRoot(int x){
	int r = x;
	while(r != set[r])
		r = set[r];

	while(x != set[x]){
		x = set[x];
		set[x] = r;
	}
	return r;
}

void MakeSet(int n){
  for(int i = 1; i <= n; i++)
    set[i] = i;
}
  
void Merge(int x, int y){
  set[x] = y;
  size[y] += size[x];
  size[x] = 0;
}
  
void Union(int x, int y){
  if(size[x] < size[y])
    Merge(x, y);
  else
    Merge(y, x);
}

void kruskal(){
	sort(G.begin(), G.end());
	MakeSet(n);
	for(int i = 0; i < m; i++){
		int x = G[i].second.first, y = G[i].second.second;
		int rootx = getRoot(G[i].second.first), rooty = getRoot(G[i].second.second);
		if(set[rootx] != set[rooty]){
			cost += G[i].first;
			arb.push_back(mk(x, y));
			Union(rootx, rooty);
		}
	}
}
  
int main(){
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m; i++){
		scanf("%d%d%d", &x, &y, &z);
		G.push_back(mk(z, mk(x, y)));
	}
	kruskal();
	printf("%d\n%d\n", cost, arb.size());
	for(int i = 0; i < arb.size(); i++)
		printf("%d %d\n", arb[i].first, arb[i].second);
    return 0;
}