#include <cstdio>
#include <cstring>
#define minim(a, b)  ((a) < (b) ? (a) : (b))

const int DM=200001,VM=200000200;
int n,m,v[DM],cost,sol[2*DM],nm=1,dimheap,nn;

struct nod {
    int x,cost;
    nod *urm;
} *varf[DM];

struct hp {
    int dela;
    int cc;//costul
    int spre;
}heap[3*DM],val;



void adaugare(int x,int y,int c) {
    nod *p;
    p=new nod;
    p->urm=varf[x];
    p->x=y;
    p->cost=c;
    varf[x]=p;
}

void upheap(int k) {
    //copiez heap[k] in val
    val.cc=heap[k].cc;
    val.dela=heap[k].dela;
    val.spre=heap[k].spre;
    heap[0].cc=-VM;
    while (heap[k/2].cc>=val.cc) {
        heap[k].cc=heap[k/2].cc;
        heap[k].dela=heap[k/2].dela;
        heap[k].spre=heap[k/2].spre;
        k/=2;
    }
    heap[k].cc=val.cc;
    heap[k].dela=val.dela;
    heap[k].spre=val.spre;
}


void downheap(int k) {
    int j;
    val.cc=heap[k].cc;
    val.dela=heap[k].dela;
    val.spre=heap[k].spre;
    while(k<=dimheap/2) {
        j=k+k;
        if(j<dimheap)
            if(heap[j].cc>heap[j+1].cc)
                j++;
        if(val.cc<=heap[j].cc) break;
        heap[k].cc=heap[j].cc;
        heap[k].dela=heap[j].dela;
        heap[k].spre=heap[j].spre;
        k=j;
    }
    heap[k].cc=val.cc;
    heap[k].dela=val.dela;
    heap[k].spre=val.spre;
}

void insert (int dela,int c,int spre) {
    ++dimheap;
    heap[dimheap].dela=dela;
    heap[dimheap].cc=c;
    heap[dimheap].spre=spre;
    upheap(dimheap);
}

/*int remove() {
    int val=a[1];
    a[1]=a[N];
    N--;
    downheap(1);
    return val;
} */

void addapm(int z) {
    nod *p;
    v[z]=1;
    --nn;
    for(p=varf[z]; p!=NULL; p=p->urm) if(!v[p->x])
            insert(z,p->cost,p->x);
    for(int i=1; i<=dimheap; i++) printf("%d ",heap[i].cc);
    printf("\n");
}

int main()
{
    int i,x,y,cost,sp;
    FILE *f=fopen("apm.in","r");
    FILE *g=fopen("apm.out","w");
    fscanf(f,"%d %d",&n,&m);
    nn=n;
    for(i=1; i<=m; i++) {//construiesc graful
        fscanf(f,"%d %d %d",&x,&y,&cost);
        adaugare(x,y,cost);
        adaugare(y,x,cost);
    }
    addapm(1);
    while(nn) {//cat timp mai am noduri
        //extrag dintre succesori pe cel mai mare
        cost+=heap[1].cc;
        sol[nm++]=heap[1].dela;
        sol[nm++]=heap[1].spre;
        sp=heap[1].spre;
        //heap[1]=heap[dimheap]+inlaturare
        heap[1].cc=heap[dimheap].cc;
        heap[1].dela=heap[dimheap].dela;
        heap[1].spre=heap[dimheap].spre;
        --dimheap;
        downheap(1);
        /////////
        addapm(sp);
    }
    --nm;
    fprintf(g,"%d\n%d\n",cost,nm/2);
    for(i=1; i<=nm; i+=2) fprintf(g,"%d %d\n",sol[i],sol[i+1]);
    return 0;
}