#include<fstream>
#include<queue>
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 main(){
    fin >> n >> m;
    for (i = 1; i <= m; i++)
        fin >> v[i].n1 >> v[i].n2 >> v[i].l;
    for (i = 1; i < m; i++)
        for (j = i + 1; j <= m; j++)
            if (v[i].l > v[j].l){
                aux = v[i];
                v[i] = v[j];
                v[j] = aux;
            }
    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';
}