// Prim.cpp : Defines the entry point for the console application.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>

using namespace std;

typedef pair<int, int> P;
#define infinit INT32_MAX;
#define Nmax 400001

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

vector <P> la[Nmax];
priority_queue< P, vector<P>, greater<P>> Q;
int nrNod, nrMuch, start;
int d[Nmax];
int viz[Nmax], tata[Nmax];

void Prim(int s) {
	for (int i = 1; i <= nrNod; i++)
		d[i] = infinit;
	d[s] = 0;
	Q.push(make_pair(d[s], s));

	while (!Q.empty()) {
		int node = (Q.top()).second;
		Q.pop();
		viz[node]++;
		if (viz[node] == 1) {
			for (int i = 0; i < la[node].size(); i++) {
				int u = la[node][i].second, w = la[node][i].first;
			
				if (!viz[u] && w < d[u]) {
					d[u] = w;
					tata[u] = node;
					Q.push(make_pair(d[u], u));
				}
			}
		}
	}
	
}

void citire() {
	in >> nrNod >> nrMuch;
	int x, y, c;
	for (int i = 1; i <= nrMuch; i++) {
		in >> x >> y >> c;
		la[x].push_back(make_pair(c, y));
		la[y].push_back(make_pair(c, x));
	}
	
}

int main()
{
	citire();
	start = 1;
	Prim(start);
	int cnt = 0;
	for (int i = 2; i <= nrNod; i++) {
		cnt += d[i];
	}
	out << cnt << '\n' << nrNod - 1 << '\n';
	for(int i = 2; i <= nrNod; i++)
		out << i << " " << tata[i] << '\n';
    return 0;
}