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

using namespace std;

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

int n, m;

struct muchie{
    int x, y, cost;
};

vector <muchie> muchii;
vector <muchie> sol;
vector <int> tati;

bool custom_comp (muchie a, muchie b)
{
    return a.cost < b.cost;
}

int radacina(int nod)
{
    if(tati[nod] != nod)
        return radacina(tati[nod]);
    else
        return nod;
}

int main() {
    fin >> n >> m;
    muchii.resize(m);
    for(int i = 0; i < m; i++)
        fin >> muchii[i].x >> muchii[i].y >> muchii[i].cost;
    for(int i = 0; i < m; i++)
        muchii[i].x--, muchii[i].y--;
    sort(muchii.begin(), muchii.end(), custom_comp);

    tati.resize(n);
    for(int i = 0; i < n; i++)
        tati[i] = i;
    for(int i = 0; i < muchii.size(); i++)
    {
        if(radacina(muchii[i].x) != radacina(muchii[i].y))
        {
            sol.push_back(muchii[i]);
            tati[radacina(muchii[i].y)] = radacina(muchii[i].x);
        }
    }

    int s = 0;
    for(int i = 0; i < sol.size(); i++)
        s += sol[i].cost;
    fout << s << '\n' << sol.size() << '\n';
    for(int i = 0; i < sol.size(); i++)
        fout << sol[i].x + 1 << ' ' << sol[i].y + 1 << '\n';

    return 0;
}