#include <bits/stdc++.h>

#define NMAX 200000
#define MMAX 400000

using namespace std;

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

struct mc{
    int a, b, c;
}muchie[MMAX + 1];

int tt[NMAX + 1];
int weight[NMAX + 1];

bool comparare(mc x, mc y){
    return x.c < y.c;
}

int headOf(int x){
    int head = x;
    while(tt[head] != head){
        head = tt[head];
    }

    //reduc drumul
    int crs = x;
    while(crs != head){
        int temp = tt[crs];
        tt[crs] = head;
        crs = temp;
    }

    return head;
}

void join(int a, int b){
    int headOfA = headOf(a);
    int headOfB = headOf(b);

    //il atasez pe ala mai mic la ala mai mare
    if(weight[headOfA] < weight[headOfB]){
        //a e mai mic
        tt[headOfA] = headOfB;
        weight[headOfB] += weight[headOfA];
    }
    else {
        tt[headOfB] = headOfA;
        weight[headOfA] += weight[headOfB];
    }
}

inline bool disjuncte(int a, int b){
    if(headOf(a) != headOf(b)){
        return true;
    }
    else {
        return false;
    }
}

int main()
{
    int N, M;
    fin >> N >> M;

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

    for(int i = 1; i <= M; i++){
        int a, b, c;
        fin >> a >> b >> c;
        muchie[i].a = a;
        muchie[i].b = b;
        muchie[i].c = c;
    }


    sort(muchie + 1, muchie + M + 1, comparare);


    vector<int> sol;
    int rez = 0;
    for(int i = 1; i <= M; i++){
        if(disjuncte(muchie[i].a, muchie[i].b)){
            rez += muchie[i].c;
            sol.push_back(i);

            join(muchie[i].a, muchie[i].b);
        }
    }

    fout << rez << "\n";
    fout << sol.size() << "\n";
    for(int i = 0; i < sol.size(); i++){
        fout << muchie[ sol[i] ].a << ' ' << muchie[ sol[i] ].b << "\n";
    }
    return 0;
}