#include <fstream>
#include <algorithm>

using namespace std;

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

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

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

int n, m, TT[200001], RN[200001], total, ult, X[400001], Y[400001];

muchie M[400001];

int root(int x)
{
    while (TT[x]!=x)
    {
        x=TT[x];
    }
    return x;
}

void unite(int x, int y)
{
    int rx=root(x);
    int ry=root(y);
    if (RN[rx]>RN[ry])
    {
        TT[ry]=rx;
        RN[rx] += RN[ry];
    }
    else
    {
        TT[rx]=ry;
        RN[ry] += RN[rx];
    }
}

int main()
{
    int i, a, b, c;
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        TT[i]=i;
        RN[i]=1;
    }
    for (i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        M[i].x=a;
        M[i].y=b;
        M[i].cost=c;
    }
    sort(M+1, M+m+1, comp);
    int s, t;
    for (i=1; i<=m; i++)
    {
        s=M[i].x;
        t=M[i].y;
        if (root(s)!=root(t))
        {
            unite(s, t);
            total+=M[i].cost;
            ult++;
            X[ult]=M[i].x;
            Y[ult]=M[i].y;
        }
    }
    fout<<total<<'\n';
    fout<<ult<<'\n';
    for (i=1; i<=ult; i++)
        fout<<X[i]<<" "<<Y[i]<<'\n';
    return 0;
}