#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct muchie
{
    int cap1, cap2, cost;
};
bool compari_cost(muchie m1, muchie m2)//ord crescatoare dupa cost
{
    if(m1.cost < m2.cost)
        return true;
    else return false;
}
int get_radacina(int x, const vector<int> &tati)
{
    while(tati[x] != -1)
        x = tati[x];
    return x;
}
void reuniune(int x, int y, vector<int> &tati, vector<int> &inaltime)
{
    int rad1 = get_radacina(x, tati);
    int rad2 = get_radacina(y, tati);
    if(inaltime[rad1] > inaltime[rad2])
    {
        tati[rad2] = rad1;
    }else
    {
        tati[rad1] = rad2;
        if(inaltime[rad1] == inaltime[rad2])
        {
            inaltime[rad2]++;
        }
    }
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n, m;
    f >> n >> m;
    muchie muc;
    vector<muchie> lista_muchii(m);
    for(int i = 0; i < m; i++)
    {
        f >> muc.cap1 >> muc.cap2 >> muc.cost;
        lista_muchii[i] = muc;
    }

    sort(lista_muchii.begin(), lista_muchii.end(), compari_cost);
    /*
    for(int i = 0; i < m; i++)
    {
        g << lista_muchii[i].cost << ": " << lista_muchii[i].cap1 << " " << lista_muchii[i].cap2 << "\n";
    }*/

    int u, v;
    int sum = 0;
    vector<muchie> sol;
    vector<int> tati(n+1, -1);
    vector<int> inaltimi(n+1, 0);

    for(int i = 0; i < m && sol.size() < n; i++)
    {
        u = lista_muchii[i].cap1;
        v = lista_muchii[i].cap2;
        if(get_radacina(u, tati) != get_radacina(v, tati))
        {
            reuniune(u, v, tati, inaltimi);
            sum = sum + lista_muchii[i].cost;
            sol.push_back(lista_muchii[i]);
        }
    }
    g << sum << "\n" << n - 1 << "\n";
    for(int i = 0; i < n; i++)
    {
        g << sol[i].cap2 << " " << sol[i].cap1 << "\n";
    }
    return 0;
}