#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector <int> apm;
int k=0,s,i,j,z,n,m,d[200010],gr[200010],v[400010],x[400010],y[400010],c[400010];
int cmp(int t1,int t2)
{
    if(c[t1]<c[t2])
        return 1;
    else
        return 0;
}
int grupa(int a)
{
    int ca=a,cb;
    while(gr[ca])
    {
        ca=gr[ca];
    }
    while(gr[a])
    {
        cb=gr[a];
        gr[a]=ca;
        a=cb;
    }
    return ca;
}
void unire(int a,int b)
{
    if(d[a]>d[b])
        gr[grupa(b)]=grupa(a);
    else
        if(d[a]<d[b])
            gr[grupa(a)]=grupa(b);
        else
        {
            gr[grupa(a)]=grupa(b);
            d[a]++;
        }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x[i]>>y[i]>>c[i];
        v[i]=i;
    }
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=m&&k<n;i++)
    {
        if(grupa(x[v[i]])!=grupa(y[v[i]]))
        {
            s+=c[v[i]];
            apm.push_back(v[i]);
            unire(x[v[i]],y[v[i]]);
            k++;
        }
    }
    g<<s<<'\n';
    g<<n-1<<'\n';
    for(i=0;i<n-1;i++)
    {
        g<<x[apm[i]]<<" "<<y[apm[i]]<<'\n';
    }
    return 0;
}