///KRUSKAL
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <algorithm>

using namespace std;

typedef pair<int, int> Pair;

struct Edge {
	int from, to, cost;
	Edge(int a, int b, int c) {
		from = a;
		to = b;
		cost = c;
	}

	Edge() {
		from = to = cost = 0;
	}
};

class Comp {public: bool operator () (const Edge& a, const Edge& b){return a.cost < b.cost;}} comp;

int find(vector<int>& st, vector<int>& rnk, int a) {
	int b = st[a];
	while(b != st[b])
		b = st[b];
	st[a] = b;
	return st[a];
}

void unite(vector<int>& st, vector<int>& rnk, int a, int b) {
	int pA = find(st, rnk, a);
	int pB = find(st, rnk, b);

	if(pA == pB) return;

	if(rnk[pA] < rnk[pB])
		st[pA] = pB;
	if(rnk[pA] > rnk[pB])
		st[pB] = pA;
	if(rnk[pA] == rnk[pB]) {
		++rnk[pA];
		st[pB] = pA;
	}
}

int kruskal(vector<Edge>& edges, int N, list<Pair>& answ) {
	sort(edges.begin(), edges.end(), comp);

	vector<int> st(N);
	vector<int> rnk(N, 0);

	for(int i=0; i<N; ++i)
		st[i] = i;

	int cost = 0;

	for(auto e : edges) {
		if(find(st, rnk, e.from) != find(st, rnk, e.to)) {
			cost += e.cost;
			unite(st, rnk, e.from, e.to);
			answ.push_back(Pair(e.from, e.to));
		}
	}
	return cost;
}

int main() {
	ifstream inStr("apm.in"); 
	ofstream outStr("apm.out");
	
	int N, M;
	inStr >> N >> M;
	
	vector<Edge> edges(M);
	
	int from, to, cost;
	for(int i=0; i<M; ++i) {
		inStr >> from >> to >> cost;
		edges.push_back(Edge(--from, --to, cost));
	}

	list<Pair> answ;
	int cst = kruskal(edges, N, answ);	

	outStr << cst << '\n' << answ.size() << '\n';

	for(auto i = answ.begin(); i != answ.end(); ++i)
		outStr << i->first+1 << ' ' << i->second+1 << '\n'; 

	return 0;
}