#include <cstdio>
#include<algorithm>
using namespace std;
int cost,n,m,i,comp[200003],v[400003];
struct rec{int x,y,c;}a[400003];
int cmp(rec a,rec b)
{
    if(a.c>b.c)return 0;
    else return 1;
}
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",&a[i].x,&a[i].y,&a[i].c);
    sort(a+1,a+1+m,cmp);
    for(i=1;i<=n;i++)
        comp[i]=i;
    for(i=1;i<=m&&v[0]==n-1;i++)
        if(comp[a[i].x]!=comp[a[i].y])
        {
            v[++v[0]]=i;
            cost+=a[i].c;
            int k=comp[a[i].y],t=comp[a[i].x];
            for(int j=1;j<=n;j++)
                if(comp[j]==k||comp[j]==t)
                comp[j]=min(k,t);
        }
    printf("%d\n%d\n",cost,v[0]);
    for(i=1;i<=v[0];i++)
        printf("%d %d\n",a[i].x,a[i].y);
    return 0;
}