#include <stdio.h>
#include <algorithm>
using namespace std;

#define Nmax 200005
#define Mmax 400005

struct edge{
    int x, y, c;
};

edge a[Mmax];
int ind[Mmax];
int r[Nmax], t[Nmax], sol[Nmax];
int n, m, cost, k;

bool comp(int i, int j)
{
    if (a[i].c < a[j].c)
        return 1;
    return 0;
}

void read()
{
    freopen("apm.in", "r", stdin);

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i){
        scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].c);
        ind[i] = i;
    }
    for (int i = 1; i <= n; ++i){
        r[i] = 1;
        t[i] = i;
    }

    fclose(stdin);
}

int find(int x)
{
    int y, z;

    for (z = x; z != t[z]; z = t[z]);
    for (; x != t[x]; ){
        y = t[x];
        t[x] = z;
        x = y;
    }

    return z;
}

void unite(int x, int y)
{
    if (r[x] > r[y])
        t[y] = x;
    else
        t[x] = y;

    if (r[x] == r[y])
        ++r[y];
}

void apm()
{
    sort(ind + 1, ind + m + 1, comp);
    for (int i = 1; i <= m; ++i){
        if ( find(a[ ind[i] ].x) != find(a[ ind[i] ].y) ){
            cost += a[ ind[i] ].c;
            unite( find(a[ ind[i] ].x), find(a[ ind[i] ].y) );
            sol[k++] = ind[i];
        }
    }
}

void write()
{
    freopen("apm.out", "w", stdout);

    printf("%d\n%d\n", cost, n - 1);
    for (int i = 0; i < k; ++i)
        printf("%d %d\n", a[ sol[i] ].x, a[ sol[i] ].y);
}

int main()
{
    read();
    apm();
    write();
}