#include <cstdio>
#include<algorithm>
using namespace std;
int cost,n,m,i,v[400003];
struct rec{int x,y,c;}a[400003];
struct rec1{int t,comp;}comp[200003];
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].t=comp[i].comp=i;
    for(i=1;i<=m&&v[0]<n-1;i++)
        if(comp[a[i].x].comp!=comp[a[i].y].comp)
        {

            v[++v[0]]=i;
            cost+=a[i].c;
            int t,k,x;
            if(comp[a[i].x].comp<comp[a[i].y].comp)
                k=a[i].x,t=a[i].y;
            else k=a[i].y,t=a[i].x;
            while(comp[k].comp!=comp[t].t)
            {
                comp[t].comp=comp[k].comp;
                x=comp[t].t;
                comp[t].t=comp[k].t;
                t=x;
            }


          /*  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[v[i]].x,a[v[i]].y);
    return 0;
}