#include <fstream>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int N,M,a[5][400001],viz[200001];
void citire()
{
    f>>N>>M;
    int i;
    for(i=1;i<=M;i++)
        f>>a[1][i]>>a[2][i]>>a[3][i];
}
void sortare()
{
    int t,i,j;
    for(i=1;i<=M;i++)
        for(j=i+1;j<=M;j++)
            if(a[3][i]>a[3][j])
                {
                    t=a[3][i];
                    a[3][i]=a[3][j];
                    a[3][j]=t;
                     t=a[2][i];
                    a[2][i]=a[2][j];
                    a[2][j]=t;
                     t=a[1][i];
                    a[1][i]=a[1][j];
                    a[1][j]=t;
                }
}
void kruskal()
{
    long cost=0;
    int k=1,i=1,nr1,nr2,j;
    sortare();
    for(i=1;i<=N;i++)
        viz[i]=i;
    i=1;
    while(k<N)
    {
        if(viz[a[1][i]]!=viz[a[2][i]])
        {
            cost+=a[3][i];
            nr1=viz[a[1][i]];nr2=viz[a[2][i]];
            for(j=1;j<=N;j++)
                if(viz[j]==nr2)
                    viz[j]=nr1;
            k++;
            a[4][i]++;
        }
        i++;
    }
    g<<cost<<'\n';
    g<<N-1<<'\n';
    for(j=1;j<i;j++)
        if(a[4][j]!=0)
            g<<a[1][j]<<" "<<a[2][j]<<'\n';
}
int main()
{
    citire();
    kruskal();
   f.close();
   g.close();
    return 0;
}