#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

struct muchie {int st,dr,cost; };

muchie v[400001],rez[400001];
int arb[200001], vc[200001];

bool comp(muchie A,muchie B){
    if(A.cost==B.cost)
        return A.st<B.dr;
    return A.cost<B.cost;
}

int main(){

    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    int i,m,n,sum=0,nrm=0,x,y,z,nr,c,j;

    scanf("%d%d",&n,&m);

    for(i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        v[i].st=x;
        v[i].dr=y;
        v[i].cost=z;
        }

    for(i=1;i<=n;i++)
        arb[i]=i;

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

    sort(v+1,v+m+1,comp);

    for(i=1;i<=m;i++){
        if( arb[v[i].st]!=arb[v[i].dr] ){

            if(vc[arb[v[i].st]]>vc[arb[v[i].dr]]){
                nr=arb[v[i].st];
                c=arb[v[i].dr];
                vc[nr]+=vc[c];
                vc[c]=0;}
            else{
                nr=arb[v[i].dr];
                c=arb[v[i].st];
                vc[nr]+=vc[c];
                vc[c]=0;
            }

            for(j=1;j<=n;j++)
                if(arb[j]==c)
                    arb[j]=nr;

            sum+=v[i].cost;
            nrm++;
            rez[nrm].st=v[i].st;
            rez[nrm].dr=v[i].dr;

            }

        }
    printf("%d\n%d\n",sum,nrm);
    for(i=1;i<=nrm;i++)
        printf("%d %d\n",rez[i].dr,rez[i].st);
    return 0;
}