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

using namespace std;

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

const int NMAX = 200001;
const int MMAX = 400001;
int N, M;
int dad[NMAX], rang[NMAX];

struct Edge{
    int n1, n2, c;
};

Edge edges[MMAX];

void init(){
    for(int i = 1; i <= N; i++){
        dad[i] = i;
        rang[i] = 0;
    }
}

void read(){
    fin >> N >> M;
    for(int i = 1; i <= M; i++){
        fin >> edges[i].n1 >> edges[i].n2 >> edges[i].c;
    }
}

int do_find(int nod){
    if(dad[nod] == nod){
        return nod;
    }
    int ans = do_find(dad[nod]);
    dad[nod] = ans;
    return ans;
}

void do_union(int nod1, int nod2){
    if(rang[nod1] < rang[nod2]){
        dad[nod1] = nod2;
    }else{
        dad[nod2] = nod1;
    }
}

int cost = 0;
int no_edges = 0;
Edge selected[NMAX];

void kruskal(){
    sort(edges + 1, edges + M + 1, [](Edge e1, Edge e2){
            return e1.c < e2.c;
         });
    for(int i = 1; i <= M; i++){
        int nod1 = edges[i].n1;
        int nod2 = edges[i].n2;
        int repr1 = do_find(nod1);
        int repr2 = do_find(nod2);
        if(repr1 != repr2){
            do_union(repr1, repr2);
            cost += edges[i].c;
            selected[++no_edges] = edges[i];
        }
    }
}

void print(){
    fout << cost << "\n";
    fout << no_edges << "\n";
    for(int i = 1; i <= no_edges; i++){
        fout << selected[i].n1 << " " << selected[i].n2 << "\n";
    }
}

int main()
{
    read();
    init();
    kruskal();
    print();
    return 0;
}