#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie
{
    int x, y;
    short c;
    bool ok;
} U[400001];

int mini, maxi, N, M;
int z[200001];

bool comp(muchie a, muchie b)
{
    return a.c < b.c;
}

int main()
{
    int i, j;

    fin>>N>>M;
    for(i = 1; i <= M; ++i)
        fin>>U[i].x>>U[i].y>>U[i].c;

    sort(U + 1, U + M + 1, comp);

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


    int nr = 0;
    int ct = 0;
    i = 1;


    while(nr < N - 1)
    {
        if(z[U[i].x] != z[U[i].y])
        {

            nr++;
            ct += U[i].c;
            U[i].ok = true;

            if(z[U[i].x] < z[U[i].y]) mini = z[U[i].x], maxi = z[U[i].y];

            else mini = z[U[i].y], maxi = z[U[i].x];

            for(j = 1; j <= N; ++j)
                if(z[j] == maxi) z[j] = mini;
        }

        ++i;
    }

    fout<<ct<<'\n';
    fout<<nr<<'\n';

    for(i = 1; i <= M; ++i)
        if(U[i].ok == true) fout<<U[i].x<<' '<<U[i].y<<'\n';

    return 0;
}