#include <fstream>
#include <algorithm>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m,i,j,k=0,Cmin=0,ii;
int Cost[400002],X[400002],Y[400002],Indice[400002],Father[200006],R[20006],Bun[200007];

int cmp(int a,int b)
{
    if(Cost[a]<Cost[b]) return 1;
    return 0;
}

int find(int x)
{
    int aux1=x,aux2;
    while(aux1!=Father[aux1]) aux1=Father[aux1];
    while(x!=Father[x])
    {
        aux2 = Father[x];
        Father[x] = aux1;
        x = aux2;
    }
    return aux1;
}

void combine(int a,int b)
{
    if(R[a]>R[b]) Father[b]=a;
    else Father[a]=b;

    if(R[a]==R[b]) R[b]++;
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>X[i]>>Y[i]>>Cost[i],Indice[i]=i;

    for(i=1;i<=n;i++)
        Father[i]=i,R[i]=1;

    sort(Indice+1,Indice+m+1,cmp);

    for(i=1;i<=m;i++)
    {
        ii=Indice[i];
        if(find(X[ii])!=find(Y[ii]))
        {
            combine( find(X[ii]) , find(Y[ii]) );
            Bun[++k]=ii;
            Cmin+=Cost[ii];
        }
    }

    g<<Cmin<<'\n'<<n-1<<'\n';

    for(i=1;i<=k;i++)
        g<<X[Bun[i]]<<' '<<Y[Bun[i]]<<'\n';

    return 0;
}