#include <iostream>

const int NMAX = 200005;

struct vertex
{
    int start;
    int value;
    int end;
    vertex *next;
};

vertex* a[NMAX];
vertex sol[NMAX];
vertex heap[NMAX];
bool result[NMAX];
int solNr = 0;

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

int N, M;
int minim = 1 << 15;
int heapSize = 0;

void swap(int i, int j)
{
    vertex v = heap[i];
    heap[i] = heap[j];
    heap[j] = v;
}

void addToHeap(vertex v)
{
    heapSize++;
    heap[heapSize] = v;
    int k = heapSize;
    while (k / 2 > 0 && heap[k].value < heap[k / 2].value)
    {
       swap(k, k / 2);
       k = k / 2;
    }
}

void addAllToHeap(int index)
{
    for (vertex* tmp = a[index]; tmp != NULL; tmp = tmp->next)
    {
        if (!result[tmp->end] || !result[tmp->start])
        {
            addToHeap(*tmp);
        }
    }
}

void removeHeap()
{
    heap[1] = heap[heapSize];
    heapSize--;
    int k = 1;
    while ((2 * k + 1 <= heapSize) && (heap[k].value > heap[2 * k].value || heap[k].value > heap[2 * k + 1].value))
    {
        if (heap[k].value > heap[2 * k].value && heap[k].value > heap[2 * k + 1].value)
        {
            if (heap[2 * k].value > heap[2 * k + 1].value)
            {
                swap(k, 2 * k + 1);
                k = 2 * k + 1;
            }
            else
            {
                swap(k, 2 * k);
                k = 2 * k;
            }
        }
        else
        {
            if (heap[k].value > heap[2 * k].value)
            {
                swap(k, 2 * k);
                k = 2 * k;
            }    
            else
            {
                swap(k, 2 * k + 1);
                k = 2 * k + 1;
            }
        }
    }
    if ((2 * k <= heapSize) && (heap[k].value > heap[2 * k].value))
    {
        swap(k, 2 * k);
        k = k * 2;
    }
}

void getNextVertex()
{
    while (result[heap[1].start] && result[heap[1].end])
    {
        removeHeap();
    }

    sol[solNr] = heap[1];
    solNr++;
    result[heap[1].start] = true;
    result[heap[1].end] = true;

    if (!result[heap[1].start])
    {
        addAllToHeap(heap[1].start);
    }
    else
    {
        addAllToHeap(heap[1].end);
    }
}

void addVertex(int x, int y, int v)
{
        vertex* tmp = new vertex;
        tmp->start = x;
        tmp->end = y;
        tmp->value = v;
        if (a[x] == NULL)
        {
            tmp->next = NULL;
            a[x] = tmp;
        }
        else
        {
            tmp->next = a[x];
            a[x] = tmp;
        }
        if (minim > x) minim = x;
}

int main(int argc, const char * argv[])
{
    fscanf(f, "%d %d", &N, &M);

    for (int i = 0; i < N; ++i)
    {
        a[i] = NULL;
        result[i] = false;
    }

    for (int i = 0; i < M; ++i)
    {
        int x, y, v;
        fscanf(f, "%d %d %d", &x, &y, &v);
        addVertex(x, y, v);
        addVertex(y, x, v);
    }

    addAllToHeap(minim);
    result[minim] = true;

    for (int i = 0; i < N - 1; ++i)
    {
        getNextVertex();
    }

    int sum = 0;
    for (int i = 0; i < solNr; ++i)
    {
        sum += sol[i].value;
    }
    fprintf(g, "%d\n", sum);
    fprintf(g, "%d\n", solNr);
    for (int i = 0; i < solNr; ++i)
    {
        fprintf(g, "%d %d\n", sol[i].start, sol[i].end);
    }

    fclose(f);
    fclose(g);
             
    return 0;
}