#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX = 200001;
const int MMAX = 400001;

struct muchie
{
    int i, j, cost;
};

int tata[NMAX], n, m, s, k;

muchie mu[MMAX], a[MMAX];

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

void citire()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> mu[i].i >> mu[i].j >> mu[i].cost;
    }
}

void kruskal()
{
    for(int i = 1; i <= n; i++)
    {
        tata[i] = i;
    }

    for(int i = 1; i <= m; i++)
    {
        int ai = tata[mu[i].i];
        int aj = tata[mu[i].j];
        if(ai != aj)
        {
            s += mu[i].cost;
            a[++k] = mu[i];
            for(int j = 1; j <= n; j++)
            {
                if(tata[j] == aj)
                    tata[j] = ai;
            }
        }

    }
}

void afisare()
{
    fout << s << '\n' << k << '\n';
    for(int i = 1; i <= k; i++)
    {
        fout << a[i].i << ' ' << a[i].j << '\n';
    }
}

int main()
{
    citire();
    sort(mu + 1, mu + m + 1, comp);
    kruskal();
    afisare();
    return 0;
}