#include <stdio.h>

int N, heapSize, heap[400001][3], nrEdges, cost, choose[200001], component[200001];
FILE *in, *out;

void heapDown(int pos)
{
    char sw;
    int next, aux;
    for(sw = 1, next = pos; sw;)
    {
        if((pos << 1) <= heapSize && heap[next][2] > heap[pos << 1][2])
            next = pos << 1;
        if((pos << 1) + 1 <= heapSize && heap[next][2] > heap[(pos << 1) + 1][2])
            next = (pos << 1) + 1;

        if(pos != next)
        {
            aux = heap[pos][0]; heap[pos][0] = heap[next][0]; heap[next][0] = aux;
            aux = heap[pos][1]; heap[pos][1] = heap[next][1]; heap[next][1] = aux;
            aux = heap[pos][2]; heap[pos][2] = heap[next][2]; heap[next][2] = aux;
            
            pos = next; 
        }
        else sw = 0;
    }
}

void popHeap(int used)
{
    int aux;
    ++nrEdges;
    aux = heap[1][0]; heap[1][0] = heap[heapSize][0]; heap[heapSize][0] = aux;
    aux = heap[1][1]; heap[1][1] = heap[heapSize][1]; heap[heapSize][1] = aux;
    heap[1][2] = heap[heapSize][2]; heap[heapSize][2] = used;
    --heapSize;
    heapDown(1);    
}

int main()
{
    int M, i, x, y;
    in = fopen("apm.in", "r");
    out = fopen("apm.out", "w");

    fscanf(in, "%d %d", &N, &M);
    for(i = 1; i <= M; i++)
        fscanf(in, "%d %d %d", &heap[i][0], &heap[i][1], &heap[i][2]);
    
    heapSize = M;
    for(i = 1; i <= N; i++)
        component[i] = i;
    for(i = (M >> 1); i; --i)
        heapDown(i);

    for(i = 0; heapSize && i < (N - 1); )
    {
        for(x = heap[1][0]; x != component[x]; x = component[x]);
        for(y = heap[1][1]; y != component[y]; y = component[y]);

        if(x != y)
        {
            if(choose[x] >= choose[y])
                component[y] = x,
                choose[x]++;
            else
                component[x] = y,
                choose[y]++;

            cost += heap[1][2];
            ++i;
            popHeap(1);
        }
        else popHeap(0);
    }
    
    fprintf(out, "%d\n%d\n", cost, i);
    for(i = M; i > heapSize; --i)
        if(heap[i][2])
            fprintf(out, "%d %d\n", heap[i][0], heap[i][1]);

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