#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
using namespace std;



typedef pair<int,int> int_pair;
int n, cost, d[200002], pred[200002];
bool viz[200002];
vector<int_pair> apm;
vector<int_pair> G[200002];
const int inf = 1 << 20;

struct comp {
	bool operator() (const int_pair& a, const int_pair& b) const {
		return a.second > b.second;
	}
};

void citire() {

	ifstream fin("apm.in");
	int m, x, y, c;
	fin >> n >> m;
	for(int i = 1; i <= m; i++) {
		fin >> x >> y >> c;
		G[x].push_back(make_pair(y, c));
		G[y].push_back(make_pair(x, c));
	}
}

void prim() {
	priority_queue<int_pair, vector<int_pair>, comp> Q;
	fill(d + 2, d + n + 1, inf);

	Q.push(make_pair(1, 0));

	for(int i = 2; i <= n; i++) {
		while (viz[Q.top().first]) {
			Q.pop();
		}

		int x = Q.top().first;
		cost += Q.top().second;
		viz[x] = true;
		Q.pop();
		
		for(int j = 0; j < G[x].size(); ++j) {
			int y = G[x][j].first, c = G[x][j].second;

			if(c < d[y] && viz[y] == false) {
				d[y] = c;
				pred[y] = x;
				Q.push(make_pair(y, c));
			}
		}
	}

	while (viz[Q.top().first]) {
		Q.pop();
	}
	cost += Q.top().second;
}

int main() {
	citire();
	
	prim();

	ofstream fout("apm.out");

	fout << cost << "\n" << n - 1 << "\n";
	for(int i = 2; i <= n; i++)
		fout << i << " " << pred[i] << "\n";

}