#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n,m,t[1000];
struct muchie{

    int i,j,cost;

}x[1000];
muchie aux;
muchie linii[100];

void citire ()
{
    fin>>n>>m;
    for(int k=1;k<=m;k++)
    {
        fin>>x[k].i>>x[k].j>>x[k].cost;
    }
    for(int i=1;i<=n;++i)
    {
        t[i]=i;
    }
}


int main()
{int i,j;
citire();
for(int i=1;i<m;i++)
{
    for(j=i+1;j<=m;j++)
    {
        if(x[i].cost>x[j].cost)
        {
            aux=x[i];
            x[i]=x[j];
            x[j]=aux;
        }
    }
}
int k=0,suma=0,p=1;
while(k<n-1)
{
    if(t[x[p].i]!=t[x[p].j])
    {
        k++;
        suma=suma+x[p].cost;
        linii[k].i=x[p].i;
        linii[k].j=x[p].j;
        linii[k].cost=x[p].cost;
        int v=t[x[p].j];
        int b=t[x[p].i];
        for(int i=1;i<=n;i++)
        {
            if(t[i]==v)
            {
                t[i]=b;
            }
        }
    }
    p++;
}
fout<<suma<<endl;
fout<<k<<endl;
for(i=1;i<=k;i++)
{
    fout<<linii[i].j<<" "<<linii[i].i<<" "<<endl;
}

return 0;
}