#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdexcept>
#include <stack>
#include <tuple>

using namespace std;

class DisjointSet {
	vector<int> parent;

	public:

		DisjointSet() {

		}


		DisjointSet(DisjointSet& S) {
			parent = S.parent;
		}

		DisjointSet(int Size) {
			parent.resize(Size);
			for (int i = 0; i < Size; i++) {
				parent[i] = i;
			}
		}

		int getRoot(const int& x) {
			int ret = x;
			while (ret != parent[ret]) {
				ret = parent[ret];
			}

			return ret;
		}

		bool merge(const int& x, const int& y) {
			int rootX = getRoot(x);
			int rootY = getRoot(y);
			if (rootX != rootY) {
				parent[rootX] = rootY;
				return true;
			}

			return false;
		}
};

class Graph
{
protected:

	int vertexNumber;
	int edgeNumber;

	vector< vector<int> > data;

	virtual void readData(istream& in);

	virtual void writeData(ostream& out);

public:

	Graph(int vertexNumber_);

	Graph(int vertexNumber_, int edgeNumber, const vector< pair<int, int> >& edges);

	virtual ~Graph();

	virtual void addEdge(const int&x, const int& y);

	friend istream& operator >> (istream& in, Graph& graph);

	friend ostream& operator << (ostream& out, Graph& graph);

};

Graph::Graph(int vertexNumber_ = 0) {
	vertexNumber = vertexNumber_;
	data.resize(vertexNumber);
}

Graph::Graph(int vertexNumber_, int edgeNumber_, const vector< pair<int, int> >& edges) {
	vertexNumber = vertexNumber_;
	edgeNumber = edgeNumber_;
	data.resize(vertexNumber);
	for (const auto& edge : edges) {
		addEdge(edge.first, edge.second);
	}
}

Graph::~Graph() {
	vertexNumber = 0;
}

void Graph::addEdge(const int& x, const int& y) {
	
	data[x].push_back(y);
	data[y].push_back(x);

}

void Graph::readData(istream& in) {
	in >> vertexNumber >> edgeNumber;
	data.clear();
	data.resize(vertexNumber);
	int a, b;
	for (int i = 0; i < edgeNumber; i++) {
		in >> a >> b;
		a--, b--;
		addEdge(a, b);
	}
}

void Graph::writeData(ostream& out) {
	out << vertexNumber << " " << edgeNumber << "\n";
	for (int v = 0; v < vertexNumber; v++) {
		for (const int& w : data[v]) {
			if (v < w) {
				out << v << " " << w << "\n";
			}
		}
	}
}

istream& operator >> (istream& in, Graph& graph) {
	graph.readData(in);
	return in;
}

ostream& operator << (ostream& out, Graph& graph) {
	graph.writeData(out);
	return out;
}

template<class DataType>
class WeightedGraph : public Graph
{
protected:

	vector< vector<DataType> > cost;

	void readData(istream& in);

	void writeData(ostream& out);

public:

	WeightedGraph(const int& vertexNumber_ = 0,const int& edgeCount_ = 0);

	~WeightedGraph();

	virtual void addEdge(const int& x, const int& y, const DataType& edgeCost);

	WeightedGraph<DataType> MinimumSpanningTree();
};

template<class DataType>
WeightedGraph<DataType>::WeightedGraph(const int& vertexNumber_ ,const int& edgeCount_) {
	vertexNumber = vertexNumber_;
	edgeNumber = edgeCount_;
	data.resize(vertexNumber);
	cost.resize(vertexNumber);
}

template<class DataType>
WeightedGraph<DataType>::~WeightedGraph() {
	vertexNumber = 0;
	edgeNumber = 0;
}


template<class DataType>
void WeightedGraph<DataType>::addEdge(const int& x, const int& y, const DataType& edgeCost) {

		data[x].push_back(y);
		data[y].push_back(x);
		cost[x].push_back(edgeCost);
		cost[y].push_back(edgeCost);		
}
template<class DataType>
WeightedGraph<DataType> WeightedGraph<DataType>::MinimumSpanningTree() {
	WeightedGraph<DataType> ret(vertexNumber, vertexNumber - 1);

	vector<bool> used(vertexNumber, false);
	vector<int> who(vertexNumber);
	vector<DataType> best(vertexNumber, numeric_limits<DataType>::max());
	priority_queue < pair< DataType, int>, vector< pair<DataType, int> > > myHeap;
	int v;
	DataType edgeCost;
	best[0] = DataType();
	myHeap.push({ DataType(), 0 });

	for (int step = 1; step <= vertexNumber; step++) {
		if (myHeap.empty()) {
			//not connected;
			return ret;
		}

		do {
			tie(edgeCost, v) = myHeap.top();
			myHeap.pop();
		} while (!myHeap.empty() && used[v]);

		if (step > 1) {
			ret.addEdge(v, who[v], edgeCost);
		}

		used[v] = true;
		for (int i = 0; i < (int)data[v].size(); i++) {
			int& w = data[v][i];
			DataType& edgeCost = cost[v][i];
			if (!used[w] && best[w] > edgeCost) {
				best[w] = edgeCost;
				who[w] = v;
				myHeap.push({ -best[w], w });
			}
		}
	}
	return ret;
}


template<class DataType>
void WeightedGraph<DataType>::readData(istream& in) {
	in >> vertexNumber >> edgeNumber;
	data.resize(vertexNumber);
	cost.resize(vertexNumber);
	int a, b;
	DataType c;

	for (int i = 0; i < edgeNumber; i++) {
		in >> a >> b >> c;
		a--, b--;
		addEdge(a, b, c);
	}
}

template<class DataType>
void WeightedGraph<DataType>::writeData(ostream& out) {

	DataType edgeCostSum = DataType();
	for (int v = 0; v < vertexNumber; v++) {
		for (int i = 0; i < (int)data[v].size(); i++) {
			if (v < data[v][i]) {
				edgeCostSum += cost[v][i];
			}
		}
	}
	out << edgeCostSum << "\n";
	out << edgeNumber << "\n";
	for (int v = 0; v < vertexNumber; v++) {
		for (int i = 0; i < (int)data[v].size(); i++) {
			if (v < data[v][i]) {
				out << v + 1 << " " << data[v][i] + 1  << "\n";
			}
		}
	}
}

int main() {

	ifstream cin("apm.in");
	ofstream cout("apm.out");
	WeightedGraph<int> G;
	cin >> G;
	WeightedGraph<int> tree = G.MinimumSpanningTree();
	cout << tree << "\n";
	return 0;
}