#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define VMAX 2e5 + 5
#define inf (0xFFFFFFFF >> 1) - 5

using namespace std;

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

vector<pair<int, int>> g[(int)VMAX], mst;
int V, E, totalWeight;

void Prim() {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	
	vector<bool> inMST(V + 1, false);
	vector<int> key(V + 1, inf), parent(V + 1, -1);

	key[1] = 0;
	pq.push({key[1], 1});
	while(!pq.empty()) {
		int u = pq.top().second;
		pq.pop();

		if(inMST[u])
			continue;

		inMST[u] = true;

		for(auto e: g[u]) {
			int v = e.first;
			int uvWeight = e.second;

			if(inMST[v] == false && key[v] > uvWeight) {
			      key[v] = uvWeight;
		      	      parent[v] = u;
			      pq.push({key[v], v});
			}
		}
	}
	
	for(int i = 1; i <= V; i++) 
		if(parent[i] != -1) {
		mst.push_back({min(i, parent[i]), max(i, parent[i])});
		totalWeight += key[i];		
	}
	
}

int main() {
	fin >> V >> E;
	for(int i = 0, u, v, weight; i < E; i++) {
		fin >> u >> v >> weight;
		g[u].push_back({v, weight});
		g[v].push_back({u, weight});
	}
	fin.close();
	
	Prim();
	
	fout << totalWeight << '\n';
	fout << mst.size() << '\n';
	for(int i = 0; i < (int)mst.size(); i++)
		fout << mst[i].first << ' ' << mst[i].second << '\n';

	fout.close();
	return 0;
}