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

#define MAXN 200001
#define MAXM 400001

struct muchie
{
    int n1,n2,cost;
}v[MAXM];
int s[MAXM],t[MAXN],n,m;

void merge(struct muchie v[], int start, int mid, int stop)
{
    int dim = stop - start + 1;
    struct muchie* aux = (struct muchie*) malloc((1 + dim) * sizeof(struct muchie));

    int i = start, j = mid + 1, k = 1;
    while (i <= mid && j <= stop)
    {
        if (v[i].cost < v[j].cost)
        {
            aux[k] = v[i];
            i++;
        }
        else
        {
            aux[k] = v[j];
            j++;            
        }
        k++;
    }

    while (i <= mid)
    {
        aux[k] = v[i];
        i++;
        k++;
    }
    while (j <= stop)
    {
        aux[k] = v[j];
        j++;
        k++;
    }

    for (i = start; i <= stop; i++)
        v[i] = aux[i - start + 1];

    free(aux);
}

void dosort(struct muchie v[], int start, int stop)
{
    if (start == stop)
        return;

    int mid = (start + stop) / 2;

    dosort(v, start, mid);
    dosort(v, mid + 1, stop);

    merge(v, start, mid, stop);
}

void sortare(struct muchie v[50],int m)
{
    dosort(v, 1, m);
}

int Kruskal(struct muchie muchii[], int t[], int in_arb[], int n)
{
    int num_muchii = 0;
    int i = 1;
    int sum = 0;
    while (num_muchii < n-1)
    {
        int u = muchii[i].n1;
        int v = muchii[i].n2;
        
        while (t[u])
            u = t[u];
        while (t[v])
            v = t[v];
        
        if (u != v)
        {
            num_muchii++;
            in_arb[i] = 1;
            t[v] = u;
            sum += muchii[i].cost;
        }

        i++;
    }

    return sum;
}

void afisare(struct muchie v[], int m,int s[])
{
    int cost = 0, cnt = 0;
    int i;
    for (i = 1; i <= m; ++i)
        if (s[i] == 1)
            cost += v[i].cost, cnt++;

    printf("%d\n%d\n", cost, cnt);
    for (i = 1; i <= m; ++i)
        if (s[i] == 1)
            printf("%d %d\n", v[i].n1, v[i].n2);
}
int main()
{
    int i;
    scanf("%d %d\n", &n, &m);
    for (i=1;i<=m;i++)
    {
        scanf("%d %d %d\n", &v[i].n1, &v[i].n2, &v[i].cost);
    }

    sortare(v,m);
    int* p = (int*) malloc(sizeof(int) * 1000000000);
    Kruskal(v,t,s,n);
    afisare(v, m,s);
    return 0;
}