#include <cstdio>
#include <algorithm>
using namespace std;
int n,m;
struct str
{
    int val;
    int n1;
    int n2;
}a[400023];
int t[200023],ct[200023];
int comp(str a,str b)
{
    return a.val<b.val;
}
int tabs(int nod)
{
    if(t[nod]!=0) return tabs(t[nod]);
    return nod;
}
int sum,nrsol;
int sol[200023][4];
int main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].n1,&a[i].n2,&a[i].val);
    sort(a+1,a+m+1,comp);
    for(int i=1;i<=n;i++) ct[i]=1;
    for(int i=1;i<=m;i++)
    {
        int t1=a[i].n1,t2=a[i].n2;
        a[i].n1=tabs(a[i].n1);
        a[i].n2=tabs(a[i].n2);
        if(a[i].n1==a[i].n2) continue;
        if(ct[a[i].n1]<=ct[a[i].n2])
        {
            t[a[i].n2]=a[i].n1;
            ct[a[i].n1]=max(ct[a[i].n2]+1,ct[a[i].n1]);
        }
        else
        {
            t[a[i].n2]=a[i].n1;
            ct[a[i].n1]=max(ct[a[i].n2]+1,ct[a[i].n1]);
        }
        sum+=a[i].val;
        ++nrsol;
        sol[nrsol][1]=t1;
        sol[nrsol][2]=t2;
    }
    printf("%d\n%d\n",sum,nrsol);
    for(int i=1;i<=nrsol;i++) printf("%d %d\n",sol[i][1],sol[i][2]);
}