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

const int NMAX = 200002;
const int MMAX = 400002;

struct Muchie{
    int i;
    int j;
    int cost;
};

Muchie Muchii[MMAX];
Muchie MuchiiAlese[MMAX];
int comp_conexa[NMAX];

bool compare(Muchie A, Muchie B){
    return A.cost < B.cost;
}

int main(){

    std::ifstream in("apm.in");
    std::ofstream out("apm.out");

    int N, M;
    in >> N >> M;

    for(int i = 1; i <= M; ++i){
        in >> Muchii[i].i >> Muchii[i].j >> Muchii[i].cost;
    }
    std::sort(Muchii + 1, Muchii + M + 1, compare);
    //for(int i = 1ș )

    for(int i = 1; i <= N; ++i){
        comp_conexa[i] = i;
    }

    int muchiiAlese = 0;
    int m = 1;
    int cost_total = 0;
    while(muchiiAlese <= N - 1 && m <= M){
        if(comp_conexa[Muchii[m].i] == comp_conexa[Muchii[m].j]){
            ++m;
        }
        else{
            MuchiiAlese[++muchiiAlese] = Muchii[m];
            cost_total += Muchii[m].cost;
            int minn, maxx;
            if(comp_conexa[Muchii[m].i] > comp_conexa[Muchii[m].j]){
                minn = comp_conexa[Muchii[m].j];
                maxx = comp_conexa[Muchii[m].i];
            }
            else{
                minn = comp_conexa[Muchii[m].i];
                maxx = comp_conexa[Muchii[m].j];
            }
            for(int i = 1; i <= N; ++i){
                if(comp_conexa[i] == maxx){
                    comp_conexa[i] = minn;
                }
            }

            ++m;
        }
    }

    out << cost_total << '\n' << N - 1 << '\n';
    for(int i = 1; i <= N - 1; ++i){
        out << MuchiiAlese[i].i << ' ' << MuchiiAlese[i].j << '\n';
    }

    return 0;
}