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

using namespace std;


const int MMAX = 4e5+1;
const int NMAX = 2e5 + 1;

struct muchie{
    int x, y, c;
};

muchie e[MMAX];
int nr[NMAX];
bool selectat[MMAX];
int t[NMAX];

bool cmp(muchie c1, muchie c2){
    return c1.c < c2.c;
}

int radacina(int x){
    if(t[x] == 0)
        return x;
    t[x] = radacina(t[x]);
    return t[x];
}

void reuniune(int x, int y){
    int rx = radacina(x);
    int ry = radacina(y);
    if(nr[rx] >= nr[ry]){
        t[ry] = rx;
        nr[rx] += nr[ry];
    }else{
        t[rx] = ry;
        nr[ry] += nr[rx];
    }
}

bool interogare(int x, int y){
    return radacina(x) == radacina(y);
}

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");

    int n, m;
    fin >> n >> m;

    for(int i = 0; i < m; i++){
        fin >> e[i].x >> e[i].y >> e[i].c;
    }

    for(int i = 0; i < n; i++){
        nr[i] = 1;
    }

    sort(e, e + m, cmp);

    int cost = 0;
    for(int i = 0; i < m; i++){
        int c1 = e[i].x;
        int c2 = e[i].y;
        if(!interogare(c1, c2)){//nu sunt in acelasi arbore
            selectat[i] = 1;
            cost += e[i].c;
            reuniune(c1, c2);
        }
    }
    fout << cost << "\n" << n - 1 << "\n";
    for(int i = 0; i < m; i++){
        if(selectat[i]){
            fout << e[i].x << " " << e[i].y << "\n";
        }
    }

    fin.close();
    fout.close();
    return 0;
}