#include <cstdio>
#include <queue>
#define Nmax 200010
using namespace std;

struct legatura
{
    int nod1,nod2,cost;
    bool operator < (const legatura &t) const
    {
        return t.cost<cost;
    }
};

int n,m,leg[Nmax],rot[Nmax];
long long rez;
priority_queue <legatura> c;

int root(int x)
{
    int beg=x,var=x,f;
    while(rot[beg]!=beg) beg=rot[beg];
    while(rot[var]!=var)
    {
        f=var;
        var=rot[var];
        rot[f]=beg;
    }
    return beg;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int i,n1,n2,price,r1,r2;
    legatura l;

    scanf("%d%d",&n,&m);
    for(;m;m--) { scanf("%d%d%d",&n1,&n2,&price); l.nod1=n1; l.nod2=n2; l.cost=price; c.push(l); }
    for(i=1;i<=n;i++) { leg[i]=i; rot[i]=i; }

    while(!c.empty())
    {
        l=c.top(); c.pop(); r1=root(l.nod1); r2=root(l.nod2);
        if(r1!=r2)
        {
            rez+=l.cost;
            leg[l.nod2]=l.nod1;
            rot[l.nod2]=r1;
            rot[r2]=r1;
        }
        /*printf("%d %d %d %d\n",l.nod1,l.nod2,r1,r2);
        for(i=1;i<=n;i++) printf("%d ",leg[i]); printf("\n");
        for(i=1;i<=n;i++) printf("%d ",rot[i]); printf("\n\n");*/
    }

    printf("%lld\n",rez);
    for(i=1;i<=n;i++)
        if(leg[i]!=i) printf("%d %d\n",i,leg[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}