#include <bits/stdc++.h>
#define inputFile "apm.in"
#define outputFile "apm.out"

using namespace std;

ifstream in(inputFile);
ofstream out(outputFile);

struct edge{
    unsigned x, y;
    short c;
};

bool cond(edge a, edge b)
{
    return a.c <= b.c;
}

int main(void)
{
    unsigned N, M;
    in >> N >> M;
    vector<edge> e(M);
    for(unsigned i = 0; i < M; ++i)
        in >> e[i].x >> e[i].y >> e[i].c;
    sort(e.begin(), e.end(), &cond);
    vector<unsigned> gr(N + 1, 0);
    unsigned cont = 0, sel = 0;
    long long costMinim = 0;
    set<pair<unsigned, unsigned> > rez;
    for(unsigned i = 0; i < M && sel + 1 < N; ++i)
    {
        if(gr[e[i].x] && gr[e[i].y] && gr[e[i].x] == gr[e[i].y])
            continue;
        if(!gr[e[i].x] && !gr[e[i].y])
            gr[e[i].x] = gr[e[i].y] = ++cont;
        else if(!gr[e[i].x])
            gr[e[i].x] = gr[e[i].y];
        else if(!gr[e[i].y])
            gr[e[i].y] = gr[e[i].x];
        else{
            unsigned elim = gr[e[i].y];
            for(unsigned j = 1; j <= N; ++j)
            if(gr[j] == elim)
                gr[j] = gr[e[i].x];
        }
        costMinim += e[i].c;
        rez.insert(make_pair(e[i].x, e[i].y));
        ++sel;
    }
    out << costMinim << '\n' << sel << '\n';
    for(auto k : rez)
        out << k.first << ' ' << k.second << '\n';
    return 0;
}