#include <cstdio>
#include <algorithm>
using namespace std;
struct nod{
int x,y,c;};
nod e[400005];
bool cmp(nod i,nod j){
return (i.c<j.c);
}
int n,m,i,j,l[200005],cost,nr,h,p,a[200005],b[200005],z;
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",&e[i].x,&e[i].y,&e[i].c);
cost=0;
for(i=1;i<=n;i++)l[i]=i;
sort(e+1,e+m+1,cmp);
i=1;nr=0;
while(i<=m && nr<n-1){
if(l[e[i].x]!=l[e[i].y]){
cost+=e[i].c;
nr++;
z++;
a[z]=e[i].x;
b[z]=e[i].y;
h=l[e[i].x];p=l[e[i].y];
for(j=1;j<=n;j++)
if(l[j]==h)l[j]=p;
}
i++;
}
printf("%d\n%d\n",cost,z);
for(i=1;i<=z;i++)
printf("%d %d\n",a[i],b[i]);
return 0;
}