#include <iostream>
#include <cstdio>
#define nmaxvf 101
#define nmaxmuchii nmaxvf(nmaxvf-1)/2

using namespace std;

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

struct muchie
{
    int e1, e2, cost;
};

muchie G[400001];
int A[200001], c[200001];
int n, m;

void Initializare()
{
    int i;
    fscanf(f, "%d%d", &n, &m);
    for(i=1; i<=m; i++)
        fscanf(f, "%d%d%d", &G[i].e1, &G[i].e2, &G[i].cost);
    for(i=1; i<=n; i++)
        c[i]=i;
}

void Afisare()
{
    int i, Scost=0;
    for(i=1; i<n; i++)
        Scost+=G[A[i]].cost;
    fprintf(g, "%d\n%d\n", Scost, n-1);
    for(i=1; i<n; i++)
        fprintf(g, "%d %d\n", G[A[i]].e1, G[A[i]].e2);
}

void Sortare()
{
    int i, j, gata;
    muchie aux;
    gata=0;
    while(gata==0)
    {
        gata=1;
        for(i=1; i<m; i++)
            if(G[i].cost>G[i+1].cost)
                {
                    gata=0;
                    aux=G[i];
                    G[i]=G[i+1];
                    G[i+1]=aux;
                }
    }
}

void Sol()
{
    int nrmsel=0, i, j, vmin, vmax;
    for(i=1; nrmsel<n-1; i++)
        if(c[G[i].e1]!=c[G[i].e2])
        {
            nrmsel++;
            A[nrmsel]=i;
            if(c[G[i].e1]<c[G[i].e2])
                {
                    vmin=c[G[i].e1];
                    vmax=c[G[i].e2];
                }
            else
                {
                    vmin=c[G[i].e2];
                    vmax=c[G[i].e1];
                }
            for(j=1; j<=n; j++)
                if(c[j]==vmax)
                    c[j]=vmin;
        }
}

int main()
{
    Initializare();
    Sortare();
    Sol();
    Afisare();
    fclose(f);
    fclose(g);
    return 0;
}