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

typedef struct
{
    int node1;
    int node2;
    int distance;
} Connection;

void SiftDown(Connection* graphConnections, int n, int index)
{
    if(index <= n)
    {
        int next1 = index * 2;
        int next2 = next1 + 1;

        if(next1 <= n)
        {
            int indexToChange = next1;

            if(next2 <= n)
            {
                if(graphConnections[next2].distance < 
                   graphConnections[next1].distance)
                {
                    indexToChange = next2;
                }
            }

            if(graphConnections[indexToChange].distance < 
               graphConnections[index].distance)
            {
                Connection tmp = graphConnections[index];
                graphConnections[index] = graphConnections[indexToChange];
                graphConnections[indexToChange] = tmp;

                SiftDown(graphConnections, n, indexToChange);
            }
        }
    }
}

void MakeHeap(Connection* graphConnections, int n)
{
    for(int i = n; i >= 1; i--)
    {
        SiftDown(graphConnections, n, i);
    }
}

Connection DeleteBest(Connection* graphConnections, int* n)
{
    Connection result = graphConnections[1];
    graphConnections[1] = graphConnections[*n];
    (*n)--;
    SiftDown(graphConnections, (*n), 1);

    return result;
}

int Find(int* nodeSet, int* childCount, int position)
{
    int index = position;

    while(nodeSet[index] != index)
    {
        index = nodeSet[index];
    }

    while(nodeSet[position] != position)
    {
        int nextVal = nodeSet[position];
        childCount[position] = 0;
        nodeSet[position] = index;
        position = nextVal;
    }

    return index;
}

void Merge(int* nodeSet, int* childCount, int node1, int node2)
{
    int root1 = Find(nodeSet, childCount, node1);
    int root2 = Find(nodeSet, childCount, node2);

    if(root1 != root2)
    {
        if(childCount[root1] < childCount[root2])
        {
            nodeSet[root1] = root2;
            childCount[root2]++;
            childCount[root2] += childCount[root1];
        }
        else
        {
            nodeSet[root2] = root1;
            childCount[root1]++;
            childCount[root1] += childCount[root2];
        }
    }
}

void Kruskal(Connection* resultConnections, int* sum, int* resultLength, Connection* graphConnections, int m, int n)
{
    int tempM = m;
    int i;

    *sum = 0;
    *resultLength = 0;

    int* nodeSet = (int*)malloc(sizeof(int) * (n + 1));
    int* childCount = (int*)malloc(sizeof(int) * (n + 1));

    for(i = 1; i <= n; i++)
    {
        nodeSet[i] = i;
    }

    for(i = 0; i < m; i++)
    {
        Connection crtConnection = DeleteBest(graphConnections, &tempM);

        int root1 = Find(nodeSet, childCount, crtConnection.node1);
        int root2 = Find(nodeSet, childCount, crtConnection.node2);

        if(root1 != root2)
        {
            Merge(nodeSet, childCount, root1, root2);
            resultConnections[(*resultLength)++] = crtConnection;
            (*sum) += crtConnection.distance;
        }
    }

    free(childCount);
    childCount = NULL;
    free(nodeSet);
    nodeSet = NULL;
}

int main(void)
{
    int i;
    int n, m;
    int finalSum;
    int resultLength;
 
    Connection* graphConnections;
    Connection* resultConnections;

    FILE* fin = fopen("apm.in", "r");
    FILE* fout = fopen("apm.out", "w");

    fscanf(fin, "%d %d", &n, &m);

    graphConnections  = (Connection*)malloc(sizeof(Connection) * (m + 1));
    resultConnections = (Connection*)malloc(sizeof(Connection) * (n - 1));

    for(i = 1; i <= m; i++)
    {
        fscanf(fin, 
               "%d %d %d", 
               &graphConnections[i].node1, 
               &graphConnections[i].node2, 
               &graphConnections[i].distance);
    }

    MakeHeap(graphConnections, m);

    Kruskal(resultConnections, &finalSum, &resultLength, graphConnections, m, n);

    fprintf(fout, "%d\n%d\n", finalSum, resultLength);

    for(int i = 0; i < resultLength; i++)
    {
        fprintf(fout, "%d %d\n", resultConnections[i].node1, resultConnections[i].node2);
    }

    free(resultConnections);
    resultConnections = NULL;

    free(graphConnections);
    graphConnections = NULL;

    fclose(fin);
    fin = NULL;
    fclose(fout);
    fout = NULL;

    return 0;
}