#include <iostream>
#include <fstream>
#include <algorithm>
#include <sstream>

#define maxN 200200
 
using namespace std;
 
ifstream fin("apm.in");
ofstream fout("apm.out");
 
struct Edge {
    int x, y, c;
} v[maxN];
int n, m, gr[maxN], nr, ans;
stringstream out;
 
void readData() {
    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
        fin >> v[i].x >> v[i].y >> v[i].c;
}
 
int getGroup(int x) {
    if (gr[x] == x) return x;
    gr[x] = getGroup(gr[x]);
    return gr[x];
}
 
void makeGroup(int x, int y) {
    gr[getGroup(x)] = getGroup(y);
}
 
bool cmp(Edge x, Edge y) {
    return x.c < y.c;
}
 
int main()
{
    readData();
    sort(v+1, v+m+1, cmp);
    for (int i = 1; i <= n; ++i)
        gr[i] = i;
    for (int i = 1; i <= m; ++i)
        if (getGroup(v[i].x) != getGroup(v[i].y))
        {
            ++nr;
            ans += v[i].c;
            makeGroup(v[i].x, v[i].y);
            out << v[i].x << ' ' << v[i].y << '\n';
        }
    fout << ans << '\n' << nr << '\n' << out.str();
    return 0;
}