#include <iostream>
#include <fstream>
#include <cstdio>

using namespace std;

ifstream f("apm.in");
FILE *g = fopen ("apm.out","w");

int m,n,muchii[4][400001],rela[200001],nrmuchii,cost;

void citire ()
{
    f>>n>>m;
    int i;
    for (i=1;i<=m;i++)
    {
        f>>muchii [0][i] >> muchii [1][i] >> muchii [2][i];
    }
}

void schimbare (int &a, int &b)
{
    int aux;
    aux= a;
    a=b;
    b=aux;
}

void sortare (int a, int b, int &m)
{
    int ai, bi;
    ai=0;
    bi =1;
    while (a <b)
    {
        if (muchii [2][a] > muchii [2][b])
        {
            schimbare (muchii [0][a],muchii [0][b]);
            schimbare (muchii [1][a],muchii [1][b]);
            schimbare (muchii [2][a],muchii [2][b]);
            schimbare (ai,bi);
        }
        a +=ai;
        b-=bi;
    }
    m= a;
}

void quicksort (int a, int b)
{
    int m;
    if (a <b)
    {
        sortare (a,b,m);
        quicksort (a,m-1);
        quicksort (m+1,b);
    }
}

void afisare_lista_muchii ()
{
    int i;
    for (i=1;i<=m;i++)
    fprintf (g ,"%d %d %d \n", muchii [0][i],muchii[1][i],muchii[2][i]);
    fprintf (g, "\n\n");

}

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

void afisare_final ()
{
    fprintf (g, "%d\n%d\n",cost , nrmuchii);
    int i;
    for (i=1;i<=m;i++)
    if (muchii [3][i] ==1)
        fprintf (g ,"%d %d\n",muchii [0][i],muchii[1][i]);
}

int main()
{
    citire ();
    quicksort (1,m);
    initializare ();
    int i=1,nmu=0,nod2,nod1,j,val2,val1;
    while (nrmuchii < n-1)
    {
        nod1= muchii [0][i];
        nod2= muchii [1][i];
        if (rela [nod1] != rela [nod2])
        {
            cost +=muchii [2][i];
            nrmuchii ++;
            muchii [3][i] = 1;
            val1= rela [nod1];
            val2= rela [nod2];
            for (j=1;j<=n;j++)
                if (rela [j] == val1)
                rela [j] =val2;
        }
        i++;
    }
    afisare_final ();
    f.close ();
    fclose (g);
    return 0;
}