#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1 + 2e5, inf =0x3f3f3f3f;

struct Edge{
	int y, c;
	Edge(int y, int c) : y(y), c(c) {}
};

vector<Edge> graph[N];
int dist[N], T[N], n;
bool use[N];

int prim(int x){
	memset(dist, inf, sizeof(dist));
	memset(use, false, sizeof(use));
	dist[x] = 0;

	while ( !use[x] ) {
		use[x] = true;
		for (Edge e : graph[x])
			if ( !use[e.y] && e.c < dist[e.y] ){
				dist[e.y] = e.c;
				T[e.y] = x;
			}
		for (int i = 1; i <= n; i++)
			if ( use[x] || !use[i] && dist[i] < dist[x] )
				x = i;
	}

	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans += dist[i];
	return ans;
}

int main(){
	ifstream in("apm.in");
	ofstream out("apm.out");
	int m, x, y, c;

	in >> n >> m;
	while (m--){
		in >> x >> y >> c;
		graph[x].emplace_back(y, c);
		graph[y].emplace_back(x, c);
	}
	out << prim(1) << '\n' << n - 1 << '\n';
	for (int i = 2; i <= n; i++)
		out << i << ' ' << T[i] << '\n';
	return 0;
}