# include <iostream>
# include <fstream>
# include <algorithm>
# include <queue>
# define nmax 400001
using namespace std;

int x[nmax], y[nmax], c[nmax], ind[nmax], p[nmax], n, m;
queue <int> coada;

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

int grupa(int x)
{
    if(p[x]==x)
        return x;
    p[x]=grupa(p[x]);
    return p[x];
}


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

void tip()
{
    for(int i=1; i<=m; i++)
        cout<<x[ind[i]]<<" "<<y[ind[i]]<<" "<<c[ind[i]]<<endl;

}

int main()
{
    f>>n>>m;

    int i;
    for(i=1; i<=m; i++)
        f>>x[i]>>y[i]>>c[i];

    for(i=1; i<=m; i++)
    {
        p[i]=i;
        ind[i]=i;
    }

    sort(ind+1, ind+m+1, cmpf);
    int nrm=1,aux1,aux2, sum=0;

    for(i=1; i<=m && nrm<n; i++)
    {
        aux1=grupa(x[ind[i]]);
        aux2=grupa(y[ind[i]]);

        if(aux1 != aux2)
        {
            p[aux2]=aux1;
            sum+=c[ind[i]];
            coada.push(ind[i]);
        }
    }

    g<<sum<<'\n'<<n-1<<'\n';
    while(!coada.empty())
    {
        i=coada.front();
        coada.pop();
        g<<x[i]<<" "<<y[i]<<'\n';
    }

    return 0;
}