#include <fstream>
#include <algorithm>

using namespace std;

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

const int nmax = 100;
int n, m, a, b, bestt, idx;

struct edge{
    int a, b, cst;

    edge() : a(0), b(0), cst(0) {};
    edge(int a, int b) : a(a), b(b), cst(0) {};
    edge(int a, int b, int cst) : a(a), b(b), cst(cst) {};

    bool operator < (const edge &obj) const {
        return cst < obj.cst;
    }
} muchii[nmax * nmax + 2];
int path[nmax + 2];

struct disjointset{
    int father[nmax + 2];
    int inset[nmax + 2];

    void init(){
        for(int i = 1; i <= n; i++){
            father[i] = i;
            inset[i] = 1;
        }
    }

    int getparent(int node){
        if(node == father[node])
            return node;
        return father[node] = getparent(father[node]);
    }

    void mergeset(int a, int b){
        a = getparent(a);
        b = getparent(b);

        if(a == b){ return; }

        if(inset[a] < inset[b])
            swap(a, b);

        father[b] = a;
        inset[a] += inset[b];
    }
} dsu;

int main(){
    in>>n>>m;
    for(int i = 1; i <= m; i++)
        in>>muchii[i].a>>muchii[i].b>>muchii[i].cst;
    sort(muchii + 1, muchii + 1 + m);

    dsu.init();
    for(int i = 1; i <= m; i++){
        a = muchii[i].a;
        b = muchii[i].b;

        if(dsu.getparent(a) != dsu.getparent(b)){
            bestt += muchii[i].cst;
            dsu.mergeset(a, b);
            path[++idx] = i;
        }
    }

    out<<bestt<<"\n"<<idx<<"\n";
    for(int i = 1; i <= idx; i++){
        out<<muchii[path[i]].a<<" "<<muchii[path[i]].b<<"\n";
    }

    return 0;
}