#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{
    int x,y,c;
};
muchie heap[400002],T[400002];
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,
    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;
        T[++k]={y,c,start[x]};
        start[x]=k;
    }

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