#include <fstream>
#include <algorithm>

using namespace std;
const int Vmax = 200001;
int tata[Vmax], a[Vmax], b[Vmax];
struct muchie{
    int x;
    int y;
    int cost;
};
muchie v[Vmax];

int findRoot(int x){
    if(tata[x]<0){
        return x;
    }
    int root = findRoot(tata[x]);
    tata[x] = root;
    return root;
}

void uniune(int x, int y){
    int rootX = findRoot(x);
    int rootY = findRoot(y);
    if(tata[rootX] < tata[rootY])
        swap(rootX, rootY);
    tata[rootY] += tata[rootX];
    tata[rootX] = rootY;
}

int main(){
    int n, m;
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin>>n>>m;
    int costArbore=0;
    int lungime=0;
    for(int i=1;i<=n;i++){
        tata[i]=-1;
    }
    for(int i=1;i<=m;i++){
        fin>>v[i].x>>v[i].y>>v[i].cost;
    }
    sort(v+1, v+m+1, [](const muchie& A, const muchie& B){
        return A.cost < B.cost;
    });
    for(int i=1;i<=m;i++){
        int x = v[i].x;
        int y = v[i].y;
        int cost = v[i].cost;
        if(findRoot(x)!=findRoot(y)){
            costArbore += cost;
            lungime++;
            a[lungime] = x;
            b[lungime] = y;
            uniune(x, y);
        }
    }
    fout<<costArbore<<'\n'<<lungime<<'\n';
    for(int i=1;i<=lungime;i++){
        fout<<a[i]<<" "<<b[i]<<'\n';
    }
}