#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct elem
{
    int in,fi,cost;
}v[400005];
struct nod
{
    int in,fi;
}sol[400005];
int n,m,t[200005],i,z,val;
bool cmp(elem a,elem b)
{
    if(a.cost==b.cost)
    {
        if(a.in==b.in)
        return a.fi<b.fi;
        return a.in<b.in;
    }
    return a.cost<b.cost;
}
int rad(int x)
{
    if(x!=t[x])
        t[x]=rad(t[x]);
    return t[x];
}
void unire(int x,int y)
{
    int r=t[x];
    t[t[x]]=t[y];
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
        t[i]=i;
    for(i=1;i<=m;i++)
        fin>>v[i].in>>v[i].fi>>v[i].cost;
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=m&&z<n;i++)
    {
        if(rad(v[i].in)!=rad(v[i].fi))
            {
                unire(v[i].in,v[i].fi);
                val+=v[i].cost;
                sol[++z].in=v[i].in;
                sol[z].fi=v[i].fi;
            }
    }
    fout<<val<<'\n';
    fout<<z<<'\n';
    for(i=1;i<=z;i++)
        fout<<sol[i].in<<' '<<sol[i].fi<<'\n';
    return 0;
}