#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int i,j,m,n,x,y,c,s,l1,l2,n1,nr,k1,xx,xx1,k,n2,a[200002],z1[200002],z2[200002];
vector <pair<int,pair<int,int> > > p;
vector <pair<int,pair<int,int> > >::iterator it;
vector <int> v[200002];
vector <int>::iterator it1;
bool ok[200002],ok1;
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        p.push_back(make_pair(c,make_pair(x,y)));
    }
    for(i=1; i<=n; i++)
    a[i]=i;
    sort(p.begin(),p.end());
    for(it=p.begin(); it!=p.end(); it++)
    {
        c=(*it).first;
        n1=((*it).second).first;
        n2=((*it).second).second;
        if(!ok[n1])
        {
            s+=c;
            z1[++k1]=n1;
            z2[k1]=n2;
            nr++;
            a[n1]=a[n2]=a[n2];
            ok[n1]=ok[n2]=true;
        }
        else
        if(!ok[n2])
        {
            s+=c;
            z1[++k1]=n1;
            z2[k1]=n2;
            nr++;
            a[n1]=a[n2]=a[n1];
            ok[n1]=ok[n2]=true;
        }
        else
        {
            xx=a[n2];
            xx1=a[n1];
            if(a[n1]!=a[n2])
            {for(i=1; i<=n; i++)
            if(a[i]==xx) a[i]=xx1;
            s+=c;
            z1[++k1]=n1;
            z2[k1]=n2;
            nr++;
            }

        }
    }
    printf("%d\n%d\n",s,nr);
    for(i=1; i<=nr; i++)
    printf("%d %d\n",z2[i],z1[i]);

    return 0;
}