#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int VAL=200005;

struct muchie
{
    int A, B, C;
};

bool operator < (const muchie &X, const muchie &Y)
{
    return X.C<Y.C;
}

muchie MCH[2*VAL];

int N, M, i, j, A, B, C;
int FAT[VAL], SUM, X, Y;
vector < pair <int, int> > SOL;

int GET_FAT(int nod)
{
    if (FAT[nod]!=nod)
        FAT[nod]=GET_FAT(FAT[nod]);
    return FAT[nod];
}

int main()
{
    fin >> N >> M;
    for (i=1; i<=M; i++)
        fin >> MCH[i].A >> MCH[i].B >> MCH[i].C;
    sort(MCH+1, MCH+M+1);
    for (i=1; i<=N; i++)
        FAT[i]=i;
    for (i=1; i<=M; i++)
    {
        X=GET_FAT(MCH[i].A);
        Y=GET_FAT(MCH[i].B);
        if (X==Y)
            continue;
        FAT[X]=Y;
        SUM+=MCH[i].C;
        SOL.push_back({MCH[i].A, MCH[i].B});
        if (SOL.size()==N-1)
            break;
    }
    fout << SUM << '\n' << N-1 << '\n';
    for (i=0; i<SOL.size(); i++)
        fout << SOL[i].first << " " << SOL[i].second << '\n';
    fin.close();
    fout.close();
    return 0;
}