#include<fstream>
#include<queue>
#include<algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie {
    int n1; int n2; int l; int luat;
};
muchie v[200008], aux;
int com[200008], n, m, i, j, k, s1, s2, cost, luate;

int cmp (muchie m1, muchie m2) {
    return m1.l < m2.l;
};

int main(){
    fin >> n >> m;
    for (i = 1; i <= m; i++)
        fin >> v[i].n1 >> v[i].n2 >> v[i].l;
    sort(v + 1, v + m + 1, cmp);
    for (i = 1; i <= n; i++)
        com[i] = i;
    k = 1; i = 1;
    while (k < n){
        if (com[v[i].n1] != com[v[i].n2]){
            k++; v[i].luat = 1; cost += v[i].l; luate++;
            s1 = com[v[i].n1];
            s2 = com[v[i].n2];
            for (j = 1; j <= n; j++)
                if (com[j] == s1)
                    com[j] = s2;
        }
        i++;
    }
    fout << cost << '\n';
    fout << luate << '\n';
    for (i = 1; i <= m; i++)
        if (v[i].luat == 1)
            fout << v[i].n1 << " " << v[i].n2 << '\n';
}