#include <bits/stdc++.h>

using namespace std;

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

int n, m;
int a, b, cost, tata[200001], cv[200001];


struct muchii{
    int a, b, cost;
}v[200001];

bool cmp(const muchii& x, const muchii& y) {
    return x.cost < y.cost;
}


int main(){
fin>>n>>m;
for (int i = 1; i <= m; i++){
    fin>>a>>b>>cost;
    v[i].a = a;
    v[i].b = b;
    v[i].cost = cost;
}
// sortam muchiile
sort(v+1, v+m+1, cmp);

for (int i = 1; i <= m; i++){
    // incepem o padura noua
    if (tata[v[i].a] == 0 && tata[v[i].b] == 0){
        tata[v[i].a] = v[i].a;
        tata[v[i].b] = v[i].a;
        cv[v[i].b] = v[i].cost;
    }
    else if (tata[v[i].a] == 0 && tata[v[i].b] != 0){
        tata[v[i].a] = v[i].b;
        cv[v[i].a] = v[i].cost;
    }
    else if (tata[v[i].a] != 0 && tata[v[i].b] == 0){
        tata[v[i].b] = v[i].a;
        cv[v[i].b] = v[i].cost;
    }
    else {
        int noda = v[i].a;
        int nodb = v[i].b;
        while (noda != tata[noda]){
            noda = tata[noda];
        }
        while (nodb != tata[nodb]){
            nodb = tata[nodb];
        }
        // am gasit ciclu
        if (noda == nodb)
            continue;

         // caz combinam 2 paduri (ineficient - poate produce arbori adanci)
        tata[noda] = nodb;
        cv[noda] = v[i].cost;
    }
}
int total = 0;
for (int i = 1; i <= n; i++){
    total += cv[i];
}
fout << total << "\n";
fout << n - 1 << "\n";
for (int i = 1; i <= n; i++){
    if (i != tata[i])
        fout << i << " " << tata[i] << "\n";
}
 
// complexitate O(n*m) worst case
// Kruskal poate fi optimizat la O(mlogm)
    return 0;
}