#include<fstream>
#include<stdlib.h>
using namespace std;
int n,m,i,viz[200002],nr,s,q;
struct nod
{
    int x,y,c,z;
};
nod v[400002];
int cmp(const void *a,const void *b)
{
    nod *nodA = (nod *)a;
    nod *nodB = (nod *)b;

    return ( nodA->c - nodB->c );
}
int main()
{
     ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].c;
        v[i].z=0;
        viz[i]=0;
    }
    qsort(v+1,m,sizeof(nod),cmp);
    s=v[1].c;
    nr=1;
    q=1;
    viz[v[1].x]=1;
    viz[v[1].y]=1;
    v[1].z=1;
    while(nr<n-1)
    {
        q++;
        if(viz[v[q].x]==0 || viz[v[q].y]==0)
        {
            s=s+v[q].c;
            viz[v[q].x]=1;
            viz[v[q].y]=1;
            v[q].z=1;
            nr++;
        }

    }
    for(i=1;i<=m;i++)
    {
        if(v[i].z==0)
        {
            s=s+v[i].c;
            v[i].z=1;
            break;
        }
    }
    fout<<s<<'\n';
    fout<<n-1<<'\n';
    for(i=1;i<=m;i++)
    {
        if(v[i].z==1)
        {
            fout<<v[i].x<<" "<<v[i].y<<'\n';
        }
    }
    return 0;
}