#include<iostream>
#include<vector>
#include<fstream>
#include<queue>
#include<algorithm>
#include<unordered_map>


using namespace std;

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

int V, E, _inf = 1<<21;


class Node {
public:
	int PrimKey = _inf, inS = 0; // distance key, flag for being in the set S 
	vector<pair<int, int>> adj;

	void add(int id, int w) {
		adj.push_back(make_pair(id, w));
	}
};


vector<Node> nodes;

void Prim() {
	// Consider the set S - initialize it with a random node
	// at each step we connect S to an exterior node through the least cost edge
	// each node will have a key which states the minimum distance it is from S

	priority_queue<tuple<int,int,int>> pq;  // dist, node start, node fin
	vector<tuple<int,int,int>> PrimMST;
	int id, i, f, w, cost = 0;

	nodes[1].inS = 1; // initialize S with first node, assume connected graph
	for (auto adj : nodes[1].adj) {
		id = adj.first, w = adj.second;
		pq.push(make_tuple(-w, 1, id)); // push edges from first node to pq, 1 is the only one in S so no need to check where edges go, those nodes are guaranteed outside of S
	}

	while (!pq.empty()) { // better condition would be MST size
		tuple<int, int, int> edge = pq.top();
		pq.pop();

		w = -get<0>(edge);
		f = get<2>(edge);

		if (nodes[f].inS) // this edge is no good, we just continue
			continue; 

		PrimMST.push_back(edge); // save this edge as it is part of the solution, should change weight back to positive but whatever
		cost += w;
		// process the node on the other side of this edge: add it to S and its outgoing edges to pq

		nodes[f].inS = 1;

		for (auto adj : nodes[f].adj) {
			id = adj.first, w = adj.second;
			if(!nodes[id].inS)
				pq.push(make_tuple(-w, f, id)); // push edges outgoing from f, if it's not ending in a node already in S
		}
	}

	cout << cost << "\n";

	cout << PrimMST.size()<<"\n";

	for (auto x : PrimMST)
		cout << get<1>(x) << " " << get<2>(x) << " \n";


}


int main() {
	int x, y, w;
	fin >> V >> E;

	nodes.resize(V+1);


	for (int i = 0; i < E; i++) {
		fin >> x >> y >> w;
		nodes[x].add(y, w);
		nodes[y].add(x, w); // undirected graph
	}

	Prim();
	
	return 0;
}