#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];
vector<int>q;
int q1[maxn];
int  tata[maxn];

bool comparator(int a, int b) {
	return d[a] > d[b];
}

int main() {

	int n, m, k = 1, total = 0;
	in >> n >> m;
	for (int i = 1; i <=n; i++)
	{
		q.push_back(i);
	}
	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 = 0;
	
	make_heap(q.begin(), q.end(),comparator);
	
	while (!q.empty()) {
		

		s = q.front();
		q1[s] = 1;
		pop_heap(q.begin(), q.end(), comparator);
		q.pop_back();
		
		
		
		

		for (auto v : ls[s]) {

			if (q1[v.first] == 0 && v.second < d[v.first]) {

				d[v.first] = v.second;
				tata[v.first] = s;
				make_heap(q.begin(), q.end(), comparator);
				
				
			}

		}
		q_size++;
		total += d[s];
	}

	out << total << "\n" << n - 1 << "\n";
	for (int i = 2; i <= n; i++)
	{
		out << i << " " << tata[i] << "\n";
	}

	return 0;
}