#include <cstdio>
#include <algorithm>
#include <queue>

#define NMAX 200001

using namespace std;

queue <int> Q;

struct muchie
{
    int x;
    int y;
    int c;
} a[NMAX];

int n;
int m;
int gr[NMAX];

bool cmp(muchie a, muchie b)
{
    return a.c < b.c;
}

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

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

int grupa(int nod)
{
    if(gr[nod] == nod)
        return nod;

    return gr[nod] = grupa(gr[nod]);
}

void reuniune(int x, int y)
{
    gr[grupa(x)] = grupa(y);
}

int solve()
{
    for(int i = 1; i <= n; gr[i] = i, ++ i);
    int s = 0;

    for(int i = 1, k = 1; i <= m && k < n; ++ i)
    {
        if(grupa(a[i].x) != grupa(a[i].y))
        {
            s += a[i].c;
            reuniune(a[i].x, a[i].y);
            Q.push(i);
            ++ k;
        }
    }

    return s;
}

void write()
{
    while(!Q.empty())
    {
        int v = Q.front();
        Q.pop();
        printf("%d %d\n", a[v].x, a[v].y);
    }
}

int main()
{
    read();
    sort(a + 1, a + m + 1, cmp);

    freopen("apm.out", "w", stdout);
    printf("%d\n%d\n", solve(), n - 1);
    write();

    return 0;
}