#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> MinimumSpanningTreeKruskal();
};

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>::MinimumSpanningTreeKruskal() {
	WeightedGraph<DataType> ret(vertexNumber, vertexNumber - 1);
	vector< tuple<DataType, int, int> > edges;
	for (int i = 0; i < vertexNumber; i++) {
		for (int j = 0; j < (int)data[i].size(); j++) {
			if (i < data[i][j]) {
				edges.push_back(make_tuple(cost[i][j], i, data[i][j]));
			}
		}
	}

	sort(edges.begin(), edges.end());
	int edgeCount = 0;
	
	DisjointSet forest(vertexNumber);

	for (auto& edge : edges) {
		DataType& c = get<0>(edge);
		int& x = get<1>(edge);
		int& y = get<2>(edge);
		if (forest.merge(x, y)) {
			edgeCount++;
			ret.addEdge(x, y, c);
			if (edgeCount == vertexNumber - 1) {
				break;
			}
		}
	}
	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.MinimumSpanningTreeKruskal();
	cout << tree << "\n";
	return 0;
}