#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,viz[200005],sum;
pair <int,int> val[400005],cord[400005],sol[400005];
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        f>>cord[i].first>>cord[i].second>>val[i].first;
        val[i].second=i;
    }
    sort(val+1,val+m+1);
    for(int i=1;i<=n;i++)
        viz[i]=i;
    int nrm=0,i=1;
    while(i<=m)
        if(viz[cord[val[i].second].first]!=viz[cord[val[i].second].second])
        {
            sum+=val[i].first;
            nrm++;
            sol[nrm].first=cord[val[i].second].first;
            sol[nrm].second=cord[val[i].second].second;
            int aux=viz[cord[val[i].second].second];
            for(int j=1;j<=n;j++)
                if(viz[j]==aux)viz[j]=viz[cord[val[i].second].first];
            i++;
        }
        else i++;
    g<<sum<<'\n';
    g<<nrm<<'\n';
    for(int j=1;j<=nrm;j++)
        g<<sol[j].first<<' '<<sol[j].second<<'\n';
    return 0;
}