#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

int n,m,sum;
int componenta[400005],x[400005],y[400005],c[400005];
int indice[400005];
vector<int> arbore;

int comp(int a)
{
    if(componenta[a]==a) return a;
    componenta[a]=comp(componenta[a]);
    return componenta[a];
}

void reuniune(int a, int b)
{
    componenta[comp(a)]=comp(b);
}

bool comp_costuri(int i,int j)
{
    return(c[i] < c[j]);
}

int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>x[i]>>y[i]>>c[i];
        indice[i]=i;
    }
    for(int i=1;i<=n;i++) componenta[i]=i;
    sort(indice+1,indice+m+1,comp_costuri);

    for(int i=1;i<=m;i++)
    {
        if(comp(x[indice[i]])!=comp(y[indice[i]]))
        {
            sum+=c[indice[i]];
            reuniune(x[indice[i]],y[indice[i]]);
            arbore.push_back(indice[i]);
        }
    }
    out<<sum<<"\n";
    out<<n-1<<"\n";
    for(int i=0;i<n-1;i++)
    {
        out<<x[arbore[i]]<<" "<<y[arbore[i]]<<"\n";
    }
    in.close();
    out.close();
    return 0;
}