#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

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

const int dimn = 200000;
const int dimm = 400000;

struct Edge {
	int adj, cost;
	Edge() {}
	Edge(int adj, int cost) {
		this->adj = adj;
		this->cost = cost;
	}
};

struct Data {
	int node, cost, parent;
	Data() {}
	Data(int node, int cost, int parent) {
		this->node = node;
		this->cost = cost;
		this->parent = parent;
	}
};

struct Comp {
	bool operator ()(const Data &a, const Data &b) {
		return a.cost > b.cost;
	}
};

priority_queue< Data, vector<Data>, Comp > heap;

int n, m;

vector<Edge> graph[dimn];

int dp[dimn], parent[dimn];
bool ok[dimn];

int main() {

	fin >> n >> m;

	for (int i = 1; i <= m; ++i) {

		int x, y, cst;
		fin >> x >> y >> cst;

		graph[x].push_back(Edge(y, cst));
		graph[y].push_back(Edge(x, cst));

	}

	for (int i = 2; i <= n; ++i)
		dp[i] = 1000000000;

	heap.push(Data(1, 0, -1));

	int minCost = 0;
	while (true) {

		while (!heap.empty() && ok[heap.top().node])
			heap.pop();

		if (heap.empty())
			break;

		int node = heap.top().node;
		parent[node] = heap.top().parent;

		ok[node] = true;

		for (vector<Edge>::iterator edge = graph[node].begin(); edge != graph[node].end(); ++edge) {

			if (dp[edge->adj] > edge->cost) {
				dp[edge->adj] = edge->cost;
				heap.push(Data(edge->adj, edge->cost, node));
			}

		}

		minCost += dp[node];

	}

	fout << minCost << '\n' << n - 1 << '\n';

	for (int i = 2; i <= n; ++i)
		fout << parent[i] << ' ' << i << '\n';

	return 0;

}

//Trust me, I'm the Doctor!