#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int Nmax = 200005;
const int Mmax = 400005;

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

struct padure{
    int root, depth;
};

muchie muchii[Mmax];
vector<muchie> sol;
padure disjoint[Nmax];

int findRoot(int nod){
    if(disjoint[nod].root == 0){
        return nod;
    }

    int root = findRoot(disjoint[nod].root);
    disjoint[nod].root = root;
    return root;
}

void Union(int x, int y){
    int r_x, r_y;

    r_x = findRoot(x);
    r_y = findRoot(y);

    if(r_x == r_y){
        return;
    }

    if(disjoint[r_x].depth > disjoint[r_y].depth){
        swap(r_x, r_y);
    }

    disjoint[r_y].depth += disjoint[r_x].depth;
    disjoint[r_x].root = r_y;
}

bool isValid(int a, int b){
    return (findRoot(a) != findRoot(b));
}

bool cmp(muchie a, muchie b){
    return a.cost < b.cost;
}

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

    int n, m, cost;

    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> muchii[i].x >> muchii[i].y >> muchii[i].cost;
    }

    sort(muchii + 1, muchii + m + 1, cmp);

    for(int i = 1; i <= n; i++){
        disjoint[i].depth = 1;
    }

    cost = 0;
    for(int i = 1; i <= m; i++){
        if(isValid(muchii[i].x, muchii[i].y)){
            cost += muchii[i].cost;
            sol.push_back(muchii[i]);
            Union(muchii[i].x, muchii[i].y);
        }
    }

    fout << cost << '\n';
    fout << sol.size() << '\n';
    for(muchie t : sol){
        fout << t.x << " " << t.y << '\n';
    }

    return 0;
}