#include <fstream>
#include <algorithm>

using namespace std;

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

struct muchie
{
    int x;
    int y;
    int cost;

} V[400002];

int N, M;
int i;

int Parinti[200002];
int nr_elem[200002];
int viz[200002];

int sum, nr_muchie;

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

int unire(int x, int y)
{
    int x1 = x;

    while(x1 != Parinti[x1])
    {
        x1 = Parinti[x1];
    }

    int x2 = x;

    while(x2 != Parinti[x2])
    {
        x2 = Parinti[x2];
        Parinti[x2] = x1;
    }

    int y1 = y;

    while(y1 != Parinti[y1])
    {
        y1 = Parinti[y1];
    }

    int y2 = y;

    while(y2 != Parinti[y2])
    {
        y2 = Parinti[y2];
        Parinti[y2] = y1;
    }

    if(nr_elem[x1] > nr_elem[y1])
    {
        Parinti[y1] = x1;
    }
    else
    {
        Parinti[x1] = y1;
    }

    nr_muchie++;

}

int parinteMax(int x)
{
    int x1 = x;

    while(x1 != Parinti[x1])
    {
        x1 = Parinti[x1];
    }

    int x2 = x;

    while(x2 != Parinti[x2])
    {
        x2 = Parinti[x2];
        Parinti[x2] = x1;
    }
    return x1;
}

int main()
{
    fin>>N>>M;

    for(i = 1; i <= M; i++)
    {
        fin>>V[i].x>>V[i].y>>V[i].cost;
    }

    sort(V + 1, V + M + 1, compare);

    for(i = 1; i<= N; i++)
    {
        Parinti[i] = i;
        nr_elem[i] = 1;
    }

    unire(V[1].x, V[1].y);
    sum += V[1].cost;
    viz[1] = 1;
    unire(V[2].x, V[2].y);
    sum += V[2].cost;
    viz[2] = 1;

    for(i = 3; i <= M; i++)
    {
        if(parinteMax(V[i].x) != parinteMax(V[i].y))
        {
            unire(V[i].x,V[i].y);
            sum += V[i].cost;
            viz[i] = 1;
        }
    }

    fout<<sum<<"\n"<<nr_muchie<<"\n";

    for(i = 1; i <= M; i++)
    {
        if(viz[i] == 1)
            fout<<V[i].x<<" "<<V[i].y<<"\n";
    }

    return 0;
}