///Pentru citire, afisare
#include <cstdio>
 
///Pentru sort
#include <algorithm>
 
using namespace std;
 
FILE *f, *g;
 
///Muchii
struct muchia {
    int st, dr;
    int c;
};
 
muchia v[400001];
 
///Componenta conexa
int comp[200001];
 
///Arborele partial de cost minim
int rez;
 
int muchie[400001];
int muchii;
 
int n, m;
 
///Citirea datelor
void readFile() {
    f = fopen("apm.in", "r");
 
    fscanf(f, "%d%d", &n, &m);
 
    int i;
    for(i = 1; i <= m; i ++)
        fscanf(f, "%d%d%d", &v[i].st, &v[i].dr, &v[i].c);
 
    fclose(f);
}
 
///Returneaza componenta conexa lui i in O(log*N);
int compConexa(int i) {
    if(comp[i] == i)
        return i;
 
    comp[i] = compConexa(comp[i]);
 
    return comp[i];
}
 
///Obtine arborele partial de cost minim
void getArb() {
    int i;
 
    for(i = 1; i <= n; i ++)
        comp[i] = i;
 
    int c1, c2;
 
    for(i = 1; i <= m; i ++) {
        ///c1, c2: Componentele conexe ale extremitatilor
        c1 = compConexa(v[i].st);
        c2 = compConexa(v[i].dr);
 
        ///Daca acestea sunt diferite (nu creeaza ciclu)
        if(c1 != c2) {
            ///Aduna costul
            rez += v[i].c;
 
            ///Unifica componentele conexe
            comp[compConexa(c1)] = compConexa(c2);
 
            ///Adauga muchia la rezultat
            muchie[++ muchii] = i;
        }
    }
}
 
///Compara costul
bool cmp(muchia a, muchia b) {
    return (a.c < b.c);
}
 
void solve() {
    ///radixSort nu merge pe negative
    sort(v + 1, v + m + 1, cmp);
 
    getArb();
}
 
void printFile() {
    g = fopen("apm.out", "w");
 
    fprintf(g, "%d\n%d\n", rez, muchii);
 
    int i, poz;
    for(i = 1; i <= muchii; i ++) {
        poz = muchie[i];
        fprintf(g, "%d %d\n", v[poz].dr, v[poz].st);
    }
 }

int main() {
    readFile();
    solve();
    printFile();
    return 0;
}