#include <fstream>
#include <algorithm>
using namespace std;
struct vct
{
    int x,y,z;
} c[400002];
struct vct2
{
    int x,y;
}afis[200002];
bool cmp (vct A , vct B)
{
    return A.z < B.z;
}
int n,m,i,a,b,d,tati[200002],s,nr,bk_a,bk_b;

int colegi(int a, int b)
{
    bk_a=a; bk_b=b;
    while(tati[a])
        a=tati[a];
    while(tati[b])
        b=tati[b];
    if(a==b)
    {
        if(tati[bk_b])
            tati[bk_b]=b;
        if(tati[bk_a])
            tati[bk_a]=a;
        return 0;
    }
    else
    {
        tati[b]=a;
        return 1;
    }
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");

    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>a>>b>>d;
        c[i].x=a;
        c[i].y=b;
        c[i].z=d;
    }
    sort(c+1,c+1+m,cmp);

    for(i=1; i<=m; i++)
        if(colegi(c[i].x,c[i].y))
            {
                s+=c[i].z;
                afis[++nr].x=c[i].x;
                afis[nr].y=c[i].y;
            }
    g<<s<<'\n';
    g<<nr<<'\n';
    for(i=1;i<=nr;i++)
    g<<afis[i].x<<' '<<afis[i].y<<'\n';

    return 0;
}