#include <iostream>
#include <algorithm>
//#include <fstream>
using namespace std;
int n,m,s,mn,arb[200005],i,p,arbc,k,j,a[400005],b[400005],ast,adr;

//ifstream cin("apm.in");
//ofstream cout("apm.out");

struct muchii
{
    int x,y,c;
} u[400005];

bool fcomp (muchii a, muchii b)
{
    return (a.c<b.c);
}

int main()
{
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>u[i].x>>u[i].y>>u[i].c;
    }
    sort(u+1,u+m+1,fcomp);
    for(i=1;i<=n;i++)
        arb[i]=i;
    s=0;k=0;
    for(i=0;i<m && k<n;i++)
    {
        if(arb[u[i].x]!=arb[u[i].y])
        {
            s=s+u[i].c;
            a[i]=u[i].x;
            b[i]=u[i].y;
            ast=arb[u[i].x]; adr=arb[u[i].y];
            for(j=1;j<=n;j++)
            {
                if(arb[j]==adr)
                    arb[j]=ast;
            }
        }
    }
    cout<<s<<'\n'<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
        cout<<a[i]<<" "<<b[i]<<'\n';
    return 0;
}