#include <fstream>
#define nmax 50006

using namespace std;

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

//KRUSKAL
//algoritm pentru determinarea arborelui partial de cost minim
//
//          APM
//
struct muchie
{
    int x, y;
    float cost;
    muchie *next;
};

muchie *A, *APM;
int N, M, CT;
int viz[nmax], c[nmax]; //in c[i] vom retine varful cu indicele cel mai mic al componentei conexe careia ii apartine vf.-ul i

void add (int x, int y, int cost)
{
    muchie *q = new muchie;

    q -> x = x;
    q -> y = y;
    q -> cost = cost;
    q -> next = A;
    A = q;
}

void read ()
{
    int i, x, y, c;

    fin >> N >> M;

    for (i = 1; i <= M; ++i)
    {
        fin >> x >> y >> c;
        add(x, y, c);
    }
}

void print_APM()
{
    muchie *q;

    q = APM;

    while (q != NULL)
    {
        fout << q -> x << " " << q -> y << "\n";
        q = q -> next;
    }
}

void swapmuchie(muchie *q, muchie *p)
{
    int a, b, c;

    a = q -> x;
    b = q -> y;
    c = q -> cost;

    q -> x = p -> x;
    q -> y = p -> y;
    q -> cost = p -> cost;

    p -> x = a;
    p -> y = b;
    p -> cost = c;

}

void sort_A()
{
    muchie *q = A;
    muchie *p;

    while (q -> next != NULL)
    {
        p = q -> next;

        while (p != NULL)
        {
            if (q -> cost > p -> cost)
                swapmuchie(q, p);
            p = p -> next;
        }
        q = q -> next;
    }
}

void addAPM(muchie *q)
{
    muchie *p = new muchie;

    p -> x = q -> x;
    p -> y = q -> y;
    p -> cost = q -> cost;

    p -> next = APM;
    APM = p;
}

void KRUSKAL()
{
    muchie *q;
    int cnt = 0, minim, maxim, i;

    for (i = 1; i <= N; ++i)
        c[i] = i;

    q = A;

    while (q != NULL && cnt < N - 1)
    {
        if (c[q -> x] != c[q -> y])
        {
            ++cnt;
            CT += q -> cost;

            //fout << c[q -> x] << " " << c[q -> y] << "\n\n";

            addAPM(q);

            if (c[q -> x] < c[q -> y])
                minim = c[q -> x], maxim = c[q -> y];
            else
                minim = c[q -> y], maxim = c[q -> x];

            for (i = 1; i <= N; ++i)
                if (c[i] == maxim)
                    c[i] = minim;
        }
        q = q -> next;

    }
}

int main()
{
    read();
    sort_A();
    KRUSKAL();

    fout << CT << "\n" << N - 1 <<"\n";
    print_APM();

    return 0;
}