#include <iostream>
#include <fstream>
using namespace std;
unsigned long long n,m,S,i,j,c[200005],k,p,t;
ifstream in("apm.in");
ofstream out("apm.out");
struct muchie
{int l1,l2,c;

}
a[500005];
struct ordine
{int p1,p2;

}
b[500005];
int main()
{in>>n>>m;
for(i=1;i<=m;i++)
{in>>a[i].l1>>a[i].l2>>a[i].c;
}
for(i=1;i<=n;i++)
c[i]=i;
for(i=1;i<m;i++)
 for(j=i+1;j<=m;j++)
    if(a[i].c>a[j].c)
        swap(a[i],a[j]);
k=0;
S=0;
i=1;
while(k<m && i<=m)
{if(c[a[i].l1]!=c[a[i].l2])
{k++;
S+=a[i].c;
t=c[a[i].l2];
    for(j=1;j<=n;j++)
        {if(c[j]==t)
        c[j]=c[a[i].l1];
        }

       b[k].p1=a[i].l1;
       b[k].p2=a[i].l2;
}
    i++;
}
out<<S<<"\n"<<k<<"\n";
for(i=1;i<=k;i++)
    {out<<b[i].p1<<" "<<b[i].p2;
out<<"\n";
    }
    return 0;
}