#include <fstream>
#include <vector>
#include <algorithm>
#define Nmax 200001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,ap[Nmax],val[Nmax],S,nr;
struct NodCost{
    int nod,nod1,cost;
}v[Nmax],sol[Nmax];
int cmp(NodCost a,NodCost b)
{
    return a.cost<b.cost;
}
int stramos(int x){
    if (ap[x]==x)
        return ap[x];
    ap[x]=stramos(ap[x]);
    return ap[x];
}
int main()
{
    int i;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>v[i].nod>>v[i].nod1>>v[i].cost;
    }
    for (i=1;i<=n;i++){
        ap[i]=i;
        val[i]=1;
    }

    sort (v+1,v+m+1,cmp);
    for (i=1;i<=m;i++)
    {
        int a1=stramos(v[i].nod);
        int b1=stramos(v[i].nod1);
        if (a1!=b1)
        {
            S+=v[i].cost;
            if (val[a1]>=val[b1])
            {
                val[a1]+=val[b1];
                ap[b1]=a1;
            }
            else
            {
                val[b1]+=val[a1];
                ap[a1]=b1;
            }
            nr++;
            sol[nr].nod=v[i].nod;
            sol[nr].nod1=v[i].nod1;
            sol[nr].cost=v[i].cost;
        }
    }
    fout<<S<<"\n"<<nr<<"\n";
    for (i=1;i<=nr;i++)
        fout<<sol[i].nod<<" "<<sol[i].nod1<<"\n";
    return 0;
}