#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m,i,j,c[200001],nrm,nod1,nod2,s,val;
struct muchie
{
    int x,y,lung,marcat;
};
muchie a[400001];

bool compar(muchie x,muchie y)
{
    if(x.lung>y.lung)
    {
        return 0;
    }
    return 1;
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a[i].x>>a[i].y>>a[i].lung;
    }
    sort(a+1,a+m+1,compar);
    for(i=1;i<=n;i++)
    {
        c[i]=i;
    }
    for(i=1;i<=m;i++)
    {
        nod1=a[i].x;
        nod2=a[i].y;
        if(c[nod1]!=c[nod2])
        {
            val=c[nod2];
            for(j=1;j<=n;j++)
            {
                if(c[j]==val)
                {
                    c[j]=c[nod1];
                }
            }
            a[i].marcat=1;
            nrm++;
        }
        if(nrm==n-1)
        {
            break;
        }
    }
    for(i=1;i<=m;i++)
    {
        if(a[i].marcat)
        {
            s=s+a[i].lung;
        }
    }
    g<<s<<endl;
    g<<n-1<<endl;
    for(i=1;i<=m;i++)
    {
        if(a[i].marcat)
        {
            g<<a[i].x<<" "<<a[i].y<<endl;
        }
    }
    return 0;
}