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

using namespace std;

const int N = 100000, M = 200000;

int n, m, nr[N], t[N], cost, nrm;
bool muchie[M];

struct element{
    int x, y, c;
}v[M];

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[rx] = ry;
        nr[ry] += nr[rx];
    }else{
        t[ry] = rx;
        nr[rx] += nr[ry];
    }
}

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

bool cmp(const element &a, const element &b){
    return a.c < b.c;
}

int main(){
    ifstream cin("apm.in");
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> v[i].x >> v[i].y >> v[i].c;
    }
    cin.close();
    sort(v, v + m, cmp);
    for(int i = 0; i < m; i++){
        if(!interogare(v[i].x, v[i].y)){
            reuniune(v[i].x, v[i].y);
            muchie[i] = true;
            nrm++;
            cost += v[i].c;
        }
    }
    ofstream cout("apm.out");
    cout << cost << '\n' << nrm << '\n';
    for(int i = 0; i < m; i++){
        if(muchie[i]){
            cout << v[i].x << ' ' << v[i].y << '\n';
        }
    }
    cout.close();
    return 0;
}