#include <bits/stdc++.h>

using namespace std;

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

int n, m, i, radx, rady, sol, cnt;
int t[400005], w[400005];

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

raihold v[400005];

bool cmp (raihold a, raihold b){
    return a.c < b.c;
}

int radacina (int a){
    while (t[a] > 0){
        a = t[a];
    }
    return a;
}

int main(){
    fin >> n >> m;
    for (i=1; i<=m; i++){
        fin >> v[i].x >> v[i].y >> v[i].c;
    }
    sort (v + 1, v + m + 1, cmp);
    for (i=1; i<=n; i++){
        t[i] = -1;
    }
    for (i=1; i<=m; i++){
        radx = radacina (v[i].x);
        rady = radacina (v[i].y);
        if (radx != rady){
            sol += v[i].c;
            w[++cnt] = i;
            if (t[radx] < t[rady]){
                t[radx] += t[rady];
                t[rady] = radx;
            }
            else{
                t[rady] += t[radx];
                t[radx] = rady;
            }
        }
    }
    fout << sol << "\n" << cnt << "\n";
    for (i=1; i<=cnt; i++){
        fout << v[w[i]].x << " " << v[w[i]].y << "\n";
    }
    return 0;
}
//recapitulare