#include <fstream>
#include <vector>
#include <limits>
#include <algorithm>
#include <string.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector <pair<int,int> >sol[200001];
int nre[200001],x,y,z,i,n,k,a[4][200001],Min,t,j,q[200001],p,u,nrm,parinte[200001],S;
bool viz[200001];
void sortare();
void df(int nod);
int main()
{
    f>>n>>k;
    for(i=1;i<=k;i++){
        f>>a[1][i]>>a[2][i]>>a[3][i];
    }
    sortare();

    for(i=1;nrm<=n-1&&i<=k;i++){
        if(parinte[a[1][i]]!=parinte[a[2][i]]||parinte[a[1][i]]==0){
            sol[a[1][i]].push_back(make_pair(a[2][i],a[3][i]));
            sol[a[2][i]].push_back(make_pair(a[1][i],a[3][i]));
            nre[a[1][i]]++;
            nre[a[2][i]]++;
            nrm++;
            a[1][nrm]=a[1][i];
            a[2][nrm]=a[2][i];
            S+=a[3][i];
            df(a[1][i]);
        }
    }
    g<<S<<'\n';
    g<<nrm<<'\n';
    for(i=1;i<=nrm;i++)
        g<<a[1][i]<<' '<<a[2][i]<<'\n';
    return 0;
}


void df(int nod){
    p=u=1;
    q[1]=nod;int nr;
    memset(viz,0,sizeof viz);
    while(p<=u){
        for(i=0;i<nre[q[p]];i++){
            nr=sol[q[p]][i].first;
            if(viz[nr]==0){
                viz[nr]=1;
                parinte[nr]=nod;
                q[++u]=nr;
            }
        }
        p++;
    }
}





void sortare(){

    for(i=1;i<=k;i++){
        Min=a[3][i];
        x=i;
        for(j=i+1;j<=k;j++)
            if(Min>a[3][j]){
                Min=a[3][j];
                x=j;
            }
        t=a[3][i];
        a[3][i]=a[3][x];
        a[3][x]=t;

        t=a[2][i];
        a[2][i]=a[2][x];
        a[2][x]=t;

        t=a[1][i];
        a[1][i]=a[1][x];
        a[1][x]=t;
    }
}