#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const int mmax=400001;
const int nmax=200001;
ifstream f("apm.in");
ofstream g("apm.out");
int grup[nmax],x[mmax],y[mmax],c[mmax],n,m;
int v[mmax],t[nmax];

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

int FindSet(int i)
{
    if (grup[i]==i) return i;
    grup[i]=FindSet(grup[i]);
    return grup[i];
}

void Union(int i,int j)
{
    grup[FindSet(i)]=FindSet(j);
}

int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x[i]>>y[i]>>c[i];
        v[i]=i;
    }
    for(i=1;i<=n;i++)
        grup[i]=i;


    sort(v+1,v+m+1,comp);

    int suma=0,K=0;
    for(i=1;i<=m;i++)
    {
        if(FindSet(x[v[i]])!=FindSet(y[v[i]]))
        {
            suma+=c[v[i]];
            Union(x[v[i]],y[v[i]]);
            t[++K]=v[i];
        }
    }
    g<<suma<<"\n";
    g<<n-1<<"\n";
    for(i=1;i<=n-1;i++)
        g<<x[t[i]]<<" "<<y[t[i]]<<"\n";
    return 0;
}