#include <fstream>
#include <algorithm>
using namespace std;

const int MAXN = 200005;
const int MAXM = 400005;

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

int n,m;

int mchx[MAXM],mchy[MAXM],costmch[MAXM];
int indicemch[MAXM];

int compconex[MAXN];//componenta conexa din care face parte nodul i
int costarbore;
int indicerasp[MAXN];
int nr_rasp;

int grupa(int x)
{
    if (compconex[x] == x)
        return x;
    compconex[x] = grupa(compconex[x]);
    return compconex[x];
}

void reunire(int x, int y)
{
    compconex[grupa(x)] = grupa(y);
}

bool ordine_buna(int i, int j)
{
    return costmch[i] < costmch[j];
}

void citire()
{
    in >> n >> m;
    for (int i = 1;i <= m;++i)
        in >> mchx[i] >> mchy[i] >> costmch[i];
}

void generare()
{
    //sortam muchiile dupa cost
    for (int i = 1;i <= m;++i)
        indicemch[i] = i;
    sort (indicemch + 1, indicemch + m + 1,ordine_buna);

    for (int i = 1;i <= n;++i)
        compconex[i] = i;//initial avem n insule

    //acum unim insulele si formam arborele
    for (int i = 1;i <= m;++i)
    {
        int ind = indicemch[i];
        int x = mchx[ind];
        int y = mchy[ind];
        int c = costmch[ind];
        if (grupa(x) != grupa(y))//adaugam muchia in arbore, astfel unim doua insule
        {
            costarbore += c;
            reunire(x,y);
            indicerasp[++nr_rasp] = ind;
        }
    }
}

void afisare()
{
    out << costarbore << '\n' << n - 1 << '\n';
    for (int i = 1;i <= nr_rasp;++i)
        out << mchx[indicerasp[i]] << ' ' << mchy[indicerasp[i]] << '\n';
}

int main()
{
    citire();
    generare();
    afisare();
    return 0;
}