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

using namespace std;

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

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

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