#include <fstream>
#include <algorithm>
#define NMAX 200010

using namespace std;

FILE *fin,*fout;

int n, m;
int MINIM, muchii;
int c[NMAX], sol[NMAX];

struct el{int x;int y;int cost;} M[2*NMAX] ;

void Kruskal();
bool comp (el a,el b)
{
    return a.cost<b.cost;
}


int main()
{
    int i;
    fin=fopen("apm.in","r");
    fout=fopen("apm.out","w");

    fscanf(fin, "%d %d", &n, &m );
    for (i=1;i<=m;i++)
        fscanf(fin,"%d %d %d",&M[i].x,&M[i].y,&M[i].cost);

    sort(M+1,M+1+m,comp);

    for (i=1;i<=n;i++)
        c[i]=i; //initializarea vectorului

    Kruskal();

    fprintf(fout,"%d\n%d\n",MINIM,n-1);
    for (i=1;i<=n-1;i++)
        fprintf(fout,"%d %d\n",M[sol[i]].x,M[sol[i]].y);
    return 0;
}

void Kruskal()
{
    int i=1,j,minim,maxim;
    while (muchii<n-1)
    {
        if (c[M[i].x]!=c[M[i].y])
        {
            MINIM=MINIM+ M[i].cost;
            muchii++;
            sol[muchii]=i;
            if(c[M[i].x]<c[M[i].y])
            {
                minim=c[M[i].x];
                maxim=c[M[i].x];
            }
            else
            {
                maxim=c[M[i].x];
                minim=c[M[i].y];
            }
            for(j=1;j<=n;j++)
                if(c[j]==maxim)
                    c[j]=minim;

        }
        i++;
    }
}