#include <fstream>
#include <stdlib.h>
using namespace std;
struct muchie
{
    int u, v, c;
};
int cmp(const void *a, const void *b)
{
    muchie *m1, *m2;
    m1=(muchie*)a;
    m2=(muchie*)b;
    return(m1->c-m2->c);
}
int n,m,g[200005],v1,v2;
muchie v[200005],a[400005];
int main ()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int i,nr,smin;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a[i].u>>a[i].v>>a[i].c;
    }
    qsort(a+1,m,sizeof(muchie),cmp);
    for(i=1;i<=n;i++)
    {
        g[i]=i;
    }
    smin=0;
    nr=0;
    for(int k=1;k<=m;k++)
    {
        if(g[a[k].u]!=g[a[k].v])
        {
            nr++;
            v[nr]=a[k];
            smin=smin+a[k].c;
            v1=g[a[k].u];
            v2=g[a[k].v];
            for(i=1;i<=n;i++)
            {
                if(g[i]==v2)
                    g[i]=v1;
            }

        }
    }
    fout<<smin<<'\n';
    fout<<nr<<'\n';
    for(i=1;i<=nr;i++)
    {
        fout<<v[i].u<<" "<<v[i].v<<" "<<'\n';
    }
    fin.close();
    fout.close();
    return 0;
}