#include <stdio.h>
#include <algorithm>
#include <vector>
#define MAX 100005
#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<int> l[MAX];
vector<muc> G;
vector<pii> arb;
  
void MakeSet(int n){
  for(int i = 1; i <= n; i++){
    set[i] = i;
    l[i].push_back(i);
  }
}
  
void Merge(int x, int y){
  while(!l[x].empty()){
    int n = l[x].back();
    l[x].pop_back();
    set[n] = y;
    l[y].push_back(n);
  }
  size[y] += size[x];
  size[x] = 0;
}
  
void Union(int x, int y){
  int fx = set[x], fy = set[y];
  if(size[fx] < size[fy])
    Merge(fx, fy);
  else
    Merge(fy, fx);
}

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;
		if(set[x] != set[y]){
			cost += G[i].first;
			arb.push_back(mk(x, y));
			Union(x, y);
		}
	}
}
  
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;
}