#include <bits/stdc++.h>
 
using namespace std;
 
struct Disjoint {
  int n;
  vector<int> sef, rang;
  
  Disjoint(int n_) : n(n_), rang(n_ + 1), sef(n_ + 1) {
		for(int i = 1; i <= n; i++) {
			sef[i] = i;
			rang[i] = 1;
		}
	}
  
  int Find(int a) {
		if(a == sef[a])
			return a;
		return sef[a] = Find(sef[a]);
	}
  
  bool Connected(int a, int b) {
    return Find(a) == Find(b);
  }
  
  void Union(int a, int b) {
		a = Find(a), b = Find(b);
		if(rang[a] > rang[b])
			swap(a, b);
		
		sef[a] = b;
		rang[b] += rang[a];
	}
};
 
struct Graph {
  struct Edge {
    int a, b, c; 
    Edge(int a_, int b_, int c_) : a(a_), b(b_), c(c_) {}
    
    bool operator<(const Edge& other) {
      return c < other.c;
    }
  };
 
  int n;
  vector<Edge> edges;
  vector<Edge> mst_edges;
 
  Graph(int n_) : n(n_) {}
 
  void AddEdge(int a, int b, int c) {
    edges.emplace_back(a, b, c);
  }
  
  int ComputeMST() {
		sort(edges.begin(), edges.end());
		
		Disjoint DS(n);
		int answer = 0;
		
		for(auto e : edges) {
			if(!DS.Connected(e.a, e.b)) {
				answer += e.c;
				DS.Union(e.a, e.b);
				mst_edges.push_back(e);
			}
		}
		
		return answer;
	}
};
 
int main() {
	ifstream cin("apm.in");
	ofstream cout("apm.out");
	
	int n, m, a, b, c;
  cin >> n >> m;

	Graph G(n);
  for(int i = 1; i <= m; i++) {
		cin >> a >> b >> c;
		G.AddEdge(a, b, c);
	}
	
	cout << G.ComputeMST() << "\n";
	cout << G.mst_edges.size() << "\n";
	for(auto e : G.mst_edges)
		cout << e.a << " " << e.b << "\n";
  
  return 0;
}