#include<cstdio>

using namespace std;

int n, m, i, cst, nume[200000], m1=0;

struct {
    int x, y, cost;
} a[400001], aux;

void qsort(int left, int right) {
    int i, j, x;

    i=left; j=right; x=a[(left+right)/2].cost;
    do {
        while (a[i].cost<x) i++;
        while (x<a[j].cost) j--;
        if (i<=j) {
            aux=a[i]; a[i]=a[j]; a[j]=aux;
            i++; --j;
        }
    } while (i<=j);

    if (i<right) qsort(i, right);
    if (j>left) qsort(left, j);
}

int alg_prim(int n, int m) {
    int j, ct, k, i, viz[200001];

    for (j=1; j<=n; ++j) viz[j]=0;
    viz[a[1].x]=viz[a[1].y]=1;
    ct=a[1].cost;

    m1++; nume[m1]=1;

    for (k=1; k<n-1; ++k) {
        i=1;
        while (viz[a[i].x]==viz[a[i].y]) ++i;

        if (viz[a[i].x]==1) viz[a[i].y]=1;
        else viz[a[i].x]=1;

        ct+=a[i].cost;
        m1++; nume[m1]=i;
    }
    return ct;
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d %d", &n, &m);

    for (i=1; i<=m; ++i)
        scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].cost);

    qsort(1,m);
    cst=alg_prim(n,m);
    printf("%d\n%d\n", cst, n-1);

    for (i=1; i<n; ++i) printf("%d %d\n", a[i].x, a[i].y);

    return 0;
}