#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;

FILE *f=fopen("apm.in","r");
FILE *g=fopen("apm.out","w");

struct s
{
    int x,y,c;
}a[400001];

bool cmp(s i,s j)
{
    return(i.c<j.c);
}

int n,m,v[100000],i,j,su,k,sol[10000];



int main()
{
    fscanf(f,"%d%d",&n,&m);

    for (i=1;i<=m;i++)
        fscanf(f,"%d%d%d",&a[i].x,&a[i].y,&a[i].c);

    sort(a+1,a+m+1,cmp);

    v[a[1].x]=1;
    v[a[1].y]=1;
    su=a[1].c;
    k=0;

    for (i=1;i<=n-2;i++)
       {
        for(j=1;j<=m;j++)
            if (v[a[j].x]!=v[a[j].y]) break;

        if (v[a[j].x]==0) v[a[j].x]=1; else v[a[j].y]=1;
        sol[++k]=j;
        su+=a[j].c;

       }

    fprintf(g,"%d\n%d\n",su,k+1);
    fprintf(g,"%d %d\n",a[1].x,a[1].y);
    for(i=1;i<=k;i++)
        fprintf(g,"%d %d\n",a[sol[i]].x,a[sol[i]].y);

    return 0;
}