#include <fstream>
#include <vector>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int N_MAX = 2e5;
const int M_MAX = 4e5;
const int HEAP_SIZE_MAX = M_MAX;
int parent[N_MAX];
vector<int> children[N_MAX];
int apm_cost = 0;

template<typename T>
class Heap{
private:
		T heap[HEAP_SIZE_MAX];
		int heapSize = 0;

		bool (* cmp)(T, T);

		inline int parent(int node){
			return (node - 1) / 2;
		}

		inline int leftChild(int node){
			return 2 * node + 1;
		}

		inline int rightChild(int node){
			return 2 * node + 2;
		}

		void upHeap(int node){
			while(node && cmp(heap[node], heap[parent(node)])){
				swap(heap[node], heap[parent(node)]);
				node = parent(node);
			}
		}

		void downHeap(int node){
			int smallest = node, left = leftChild(node), right = rightChild(node);

			if(left < heapSize && cmp(heap[left], heap[smallest]))
				smallest = left;
			if(right < heapSize && cmp(heap[right], heap[smallest]))
				smallest = right;

			if(smallest != node){
				swap(heap[smallest], heap[node]);
				downHeap(smallest);
			}
		}

public:

		Heap(bool (* _cmp)(T, T)) : cmp(_cmp){}

		void build(int n, ifstream& fin){
			heapSize = n;
			for(int i = 0; i < n; ++i)
				fin >> heap[i];

			int firstNoLeaf = n / 2 - 1;
			for(int node = firstNoLeaf; node >= 0; --node)
				downHeap(node);
		}

		T query(){
			return heap[0];
		}

		void extractRoot(){
			swap(heap[0], heap[heapSize - 1]);
			--heapSize;
			downHeap(0);
		}

		bool empty(){
			return !heapSize;
		}
};

struct Edge{
		int to, from;
		short cost;

		friend ifstream& operator>>(ifstream& fin, Edge& self){
			fin >> self.from >> self.to >> self.cost;
			--self.from, --self.to;

			return fin;
		}
};

void initDSU(int n){
	for(int i = 0; i < n; ++i)
		parent[i] = i;
}

int find(int x){
	if(parent[x] == x)
		return x;
	return parent[x] = find(parent[x]);
}

bool unite(int x, int y, short cost){
	bool retval = false;
	int parentx = find(x);
	int parenty = find(y);

	if(parentx != parenty){
		parent[parenty] = parentx;
		children[x].push_back(y);
		apm_cost += cost;
		retval = true;
	}

	return retval;
}

bool cmp(Edge a, Edge b){
	return a.cost < b.cost;
}

Heap<Edge> heap(cmp);

void Kruskal(int nodes, int edges){
	initDSU(nodes);
	heap.build(edges, fin);

	int conex_components = nodes;
	Edge min;

	while(!heap.empty() && conex_components > 1){
		min = heap.query();
		heap.extractRoot();

		conex_components -= unite(min.from, min.to, min.cost);
	}
}

int main(){
	int nodes, edges;
	fin >> nodes >> edges;

	Kruskal(nodes, edges);

	fout << apm_cost << '\n' << nodes - 1 << '\n';
	for(int node = 0; node < nodes; ++node)
		for(auto child: children[node])
			fout << node + 1 << ' ' << child + 1 << '\n';

	fin.close();
	fout.close();
	return 0;
}