#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m;
struct edge {
int i, j, cost;
};
edge a[201];
int t[201];
int final_sum = 0;
int edgeCount = 1;
void read() {
fin >> n >> m;
for (int i = 1; i <= m; i++)
fin >> a[i].i >> a[i].j >> a[i].cost;
}
/// verif citire valori
void debug() {
for (int i = 1; i <= m; i++)
fout << a[i].i << " " << a[i].j << " " << a[i].cost << "\n";
}
bool cmp(edge x, edge y) {
if (x.cost < y.cost) return true;
else return false;
}
void init() {
for (int i = 1; i <= n; i++) t[i] = i;
}
void reunion(int i, int j) {
for (int k = 1; k <= n; k++) {
if (t[k] == j) t[k] = i;
}
}
int b[201][3];
void APM() {
for(int i = 0; i < m ; i++)
if(t[a[i].i] != t[a[i].j]) {
final_sum += a[i].cost;
int ii = t[a[i].i], jj = t[a[i].j];
reunion(ii, jj);
edgeCount++;
b[edgeCount][1] = a[i].j;
b[edgeCount][2] = a[i].i;
}
}
int main()
{
read();
sort(a, a + m + 1, cmp);
init();
APM();
fout << final_sum << "\n" << edgeCount << "\n";
for (int i = 1; i <= m; i++) {
if (b[i][1] == 0 || b[i][2] == 0) continue;
fout << b[i][2] << " " << b[i][1] << "\n";
}
//debug();
return 0;
}