#include <fstream>
#include <algorithm>
#define NMAX 200005
#define MMAX 400005

using namespace std;

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

struct muchie
{
    int x, y, c;
} G[MMAX];

int n, m, cost;
int conex[NMAX]; ///conex[i] = componenta conexa din care face parte i
int A[NMAX]; ///indicii muchiilor selectate in arbori

void citire();
void kruskal();
void sortare();
void afisare();
bool compar(muchie, muchie);

int main()
{
    citire();
    kruskal();
    afisare();
}

void citire()
{
    fin>>n>>m;

    for(int i=1; i <= m; i++)
        fin>>G[i].x>>G[i].y>>G[i].c;
}

void kruskal()
{
    ///ordonez muchiile crescator dupa cost
    sort(G + 1, G + m + 1, compar);
    int nrsel = 0, i;
    for(i=1; i <= n; i++)
        conex[i] = i;

    i = 1;

    while(nrsel < n - 1)
    {
        if(conex[G[i].x] != conex[G[i].y])
        {
            nrsel++;
            A[nrsel] = i;
            cost += G[i].c;
            ///unificam componentele conexe ale extremitatilor

            int cx = conex[G[i].x];
            int cy = conex[G[i].y];

            for(int j=1; j <= n; j++)
                if(conex[j] == cy)
                    conex[j] = cx;
        }
        i++;
    }
}

/*void sortare()
{
    bool sch;

    do
    {
        sch = false;

        for(int i=1; i < m; i++)
            if(G[i].c > G[i+1].c)
            {
                swap(G[i], G[i+1]);
                sch = true;
            }
    }
    while(sch);
}*/

void afisare()
{
    fout<<cost<<endl<<n - 1<<endl;
    for(int i=1; i < n; i++)
        fout<<G[A[i]].x<<' '<<G[A[i]].y<<endl;
}

bool compar(muchie A, muchie B)
{
    return A.c < B.c;
}