#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int maxn = 200100,minn=999999999;

vector<pair<int,int>>ls[maxn];
int d[maxn];
int q[maxn],tata[maxn];
int main() {

	int n, m, k = 0, total = 0;
	in >> n >> m;
	while (m--) {
		int v1, v2, c;
		in >> v1 >> v2 >> c;
		ls[v2].push_back({ v1,c });
		ls[v1].push_back({ v2,c });
		d[v1] = minn;
		d[v2] = minn;

	}
	int s = 1;
	d[s] = 0;
	int q_size = n;
	while (q_size != 0) {
		int minim = minn + 1,cost=0;
		
		
		for (int i = 1; i <= n; i++)
		{
			if (q[i]==0&&d[i] < minim) {
				s = i;
				minim = d[i];
			}
		}
		q_size--;
		q[s] = 1;
		
		for (auto v : ls[s]) {
			
			if (q[v.first] == 0 && v.second < d[v.first]) {
				
				d[v.first] = v.second;
				tata[v.first] = s;
				cost = v.second;
				
				
			}
			
		}
		total += d[s];
	}
	out << total << "\n" << n - 1 << "\n";
	for (int i = 2; i <= n; i++)
	{
		out << i << " " << tata[i] << "\n";
	}

	return 0;
}