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

int n, m, i, j, k, a, b, c, gasit, viz[200010];
long long s;
struct muchie
{
    int a, b, c;
    bool bn;
}M[400100];

bool criteriu(muchie a,muchie b)
{
    if(a.c<=b.c)
        return 1;
    else
        return 0;
}

int main()
{
    fin >> n>> m;
    for(i=1;i<=m;++i)
    {
        fin >> M[i].b>> M[i].a>> M[i].c;
    }
    sort(M+1,M+m+1,criteriu);


    for(j=1;j<=n;++j)
    {
        viz[j]=j;
    }

    int mare;
    i=1;
    j=0;
        for(i=1;j<n-1;++i)
        {
            if(viz[M[i].a]!=viz[M[i].b])
            {
                ++j;
                M[i].bn=1;
                if(viz[M[i].a]<viz[M[i].b])
                    mare=viz[M[i].b];
                else
                    mare=viz[M[i].a];
                for(k=1;k<=n;++k)
                {
                    if(viz[k]==viz[M[i].a]||viz[k]==viz[M[i].b])
                        viz[k]=mare;
                }
            }
        }

    for(i=1;i<=m;++i)
    {
        if(M[i].bn)
            s+=M[i].c;
    }
    fout<< s<<'\n';

    fout<< n-1<<'\n';
    for(i=1;i<=m;++i)
    {
        if(M[i].bn)
            fout<< M[i].a<<" "<<M[i].b<<'\n';
    }
    return 0;
}