#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
struct data {
int c, x, y;
}g[500001];
int r[500001], sol[500001][3], n, m, p, cost, muchii;
int grupa(int i) {
if(r[i] == i) return i;
r[i] = grupa(r[i]);
return r[i];
}
void reuniune(int i, int j) {
r[grupa(i)] = grupa(j);
}
inline bool cmp(data a, data b) {
return a.c < b.c;
}
int main() {
int i, x, y, c;
ifstream fin("apm.in");
ofstream fout("apm.out");
fin >> n >> m;
for(i = 1; i <= m; ++i) {
fin >> x >> y >> c;
g[++p] = data{c, x, y};
}
sort(g + 1, g + m + 1, cmp);
for(i = 1; i <= n; ++i)
r[i] = i;
for(i = 1, p = 0; i <= m; ++i) {
if(grupa(g[i].x) != grupa(g[i].y)) {
reuniune(g[i].x, g[i].y);
cost += g[i].c; ++muchii;
sol[++p][1] = g[i].x; sol[p][2] = g[i].y;
}
}
fout << cost << '\n' << muchii << '\n';
for(i = 1; i <= p; ++i)
fout << sol[i][1] << ' ' << sol[i][2] << '\n';
fout.close();
return 0;
}