#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{
    int x,y,c;
};
muchie heap[800002];
int nheap;
void urcare(int p){
    while(p/2>=1 && heap[p/2].c>heap[p].c){
        muchie aux=heap[p];heap[p]=heap[p/2];heap[p/2]=aux;
        p=p/2;
    }
}
void coborare(int p){
    int r;
    while(2*p<=nheap){
        r=2*p;
        if(r+1<=nheap && heap[r+1].c<heap[r].c)r++;
        if(heap[p].c>heap[r].c){
            muchie aux=heap[p];heap[p]=heap[r];heap[r]=aux;
            p=r;
        }
        else break;
    }
}
int m,start[200002],i,n,vmin,j,k,
    T[3][800002],c,x,y,viz[200002],
    tata[200002],infinit=1000000000;
int main()
{
    fin>>n>>m;
    k=0;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        k++;
        T[0][k]=y;
        T[1][k]=c;
        T[2][k]=start[x];
        start[x]=k;
        k++;
        T[0][k]=x;
        T[1][k]=c;
        T[2][k]=start[y];
        start[y]=k;

    }
    for(i=1;i<=n;i++)
    {
        viz[i]=0;
    }

    tata[1]=0;
    nheap=0;
    viz[1]=1;
    for(j=start[1];j;j=T[2][j]){
        nheap++;
        heap[nheap].x=1;
        heap[nheap].y=T[0][j];
        heap[nheap].c=T[1][j];
        urcare(nheap);
    }
    int s=0;
    for(i=2;i<=n;i++)
    {
        while(viz[heap[1].x]==1 && viz[heap[1].y]==1){
            heap[1]=heap[nheap];
            nheap--;
            coborare(1);
        }
        if(viz[heap[1].x]==0){
            k=heap[1].x;
            tata[k]=heap[1].y;
        }
        else{
            k=heap[1].y;
            tata[k]=heap[1].x;
        }
        viz[k]=1;
        s=s+heap[1].c;

        for(j=start[k];j!=0;j=T[2][j])
        {
            y=T[0][j];
            c=T[1][j];
            if(viz[y]==0)
            {
                nheap++;
                heap[nheap].x=k;
                heap[nheap].y=y;
                heap[nheap].c=c;
                urcare(nheap);
            }
        }
    }
    fout<<s<<"\n";
    fout<<n-1<<"\n";
    for(i=2;i<=n;i++)
    {
        fout<<i<<" "<<tata[i]<<"\n";
    }
    return 0;
}