#include <stdio.h>
#include <stdlib.h>

#define INF 999999999
#define NRMAXNODURI 800

#define IN "apm.in"
#define OUT "apm.out"

int muchii[2 * (NRMAXNODURI - 1)];
int cost = 0;
int index = 0;

typedef struct
{
    int nrNoduri;
    int matAdiacenta[NRMAXNODURI][NRMAXNODURI];
    int U[NRMAXNODURI];
    int S[NRMAXNODURI];
} Graf;

Graf graf;

void initGraf(Graf *g)
{
    g->nrNoduri = 0;
    for (int i = 0; i < NRMAXNODURI; i++)
    {
        g->U[i] = 0;
        g->S[i] = i;
        for (int j = 0; j < NRMAXNODURI; j++)
        {
            g->matAdiacenta[i][j] = 0;
        }
    }
}

void adaugaArcNeorientat(Graf *g, int i, int j, int pondere)
{
    g->matAdiacenta[i][j] = g->matAdiacenta[j][i] = pondere;
}

void prim(Graf *g, int indexNod)
{
    g->U[indexNod] = 1;
    for (int pas = 0; pas < g->nrNoduri - 1; pas++)
    {
        int minim = INF, minI = -1, minJ = -1;
        for (int i = 0; i < g->nrNoduri; i++)
        {
            if (g->U[i] == 1)
            {
                for (int j = 0; j < g->nrNoduri; j++)
                {
                    if (g->matAdiacenta[i][j] != 0 && g->U[j] == 0 && g->matAdiacenta[i][j] < minim)
                    {
                        minim = g->matAdiacenta[i][j];
                        minI = i;
                        minJ = j;
                    }
                }
            }
        }
        if (minI != -1 && minJ != -1)
        {
            g->U[minJ] = 1;
            cost = cost + minim;
            muchii[index] = minI + 1;
            index = index + 1;
            muchii[index] = minJ + 1;
            index = index + 1;
        }
    }
}

void kruskal(Graf *g)
{
    for (int pas = 0; pas < g->nrNoduri - 1; pas++)
    {
        int minim = INF, minI = -1, minJ = -1;
        for (int i = 0; i < g->nrNoduri; i++)
        {
            for (int j = 0; j < g->nrNoduri; j++)
            {
                if (g->matAdiacenta[i][j] != 0 && g->S[i] != g->S[j] && g->matAdiacenta[i][j] < minim)
                {
                    minim = g->matAdiacenta[i][j];
                    minI = i;
                    minJ = j;
                }
            }
        }
        if (minI != -1 && minJ != -1)
        {
            int multimeVeche = g->S[minJ], multimeNoua = g->S[minI];
            for(int k = 0; k < g->nrNoduri; k++)
            {
                if(g->S[k] == multimeVeche)
                {
                    g->S[k] = multimeNoua;
                }
            }
            cost = cost + minim;
            muchii[index] = minI + 1;
            index = index + 1;
            muchii[index] = minJ + 1;
            index = index + 1;
        }
    }
}

int main(void)
{
    FILE *in, *out;
    in = fopen(IN, "r");
    out = fopen(OUT, "w");

    int nrMuchii, i, j, pondere;

    initGraf(&graf);

    fscanf(in, "%d", &graf.nrNoduri);
    fscanf(in, "%d", &nrMuchii);
    for (int k = 0; k < nrMuchii; k++)
    {
        fscanf(in, "%d %d %d", &i, &j, &pondere);
        adaugaArcNeorientat(&graf, i - 1, j - 1, pondere);
    }

    //prim(&graf, 0);
    kruskal(&graf);

    fprintf(out, "%d\n", cost);
    fprintf(out, "%d\n", graf.nrNoduri - 1);
    for (int i = 0; i < index; i = i + 2)
    {
        fprintf(out, "%d %d\n", muchii[i], muchii[i + 1]);
    }

    fclose(in);
    fclose(out);
    return 0;
}