#include <fstream>
#include <algorithm>

using namespace std;

const int nmax = 200100;
const int mmax = 400100;

int TT[nmax], Rg[nmax], Sol[nmax][2], E[mmax][3], sir[mmax];

int find(int a)
{
    if(a != TT[a]) return TT[a] = find(TT[a]);
    return a;
}

void Unite(int a, int b)
{
    if(Rg[a] > Rg[b])
        TT[b] = a;
    else TT[a] = b;

    if(Rg[a] == Rg[b])
        Rg[b]++;
}

struct cmp
{
    bool operator()(const int &a, const int &b)const
    {
        return E[a][2] < E[b][2];
    }
};

int N, M, cat;

int main()
{
    ifstream in("apm.in");

    in >> N >> M;
    int i, first, second;
    for(i = 1; i <= M; i++)
    {
        in >> E[i][0] >> E[i][1] >> E[i][2];
        sir[i] = i;
    }

    sort(sir + 1, sir + 1 + M, cmp());

    for(i = 1; i <= N; i++)
    {
        TT[i] = i;
        Rg[i] = 1;
    }

    int S = 0;
    for(i = 1; i <= M && cat < N - 1; i++)
    {
        first = find(E[sir[i]][0]);
        second = find(E[sir[i]][1]);

        if(first != second)
        {
            Unite(first, second);
            Sol[++cat][0] = E[sir[i]][0];
            Sol[cat][1] = E[sir[i]][1];
            S += E[sir[i]][2];
        }
    }

    ofstream out("apm.out");
    out << S << '\n' << cat << '\n';
    for(i = 1; i <= cat; i++)
        out << Sol[i][0] << ' ' << Sol[i][1] << '\n';

    return 0;
}