#include <cstdio>
#include <algorithm>

using namespace std;
FILE* f, * g;

struct name
{
    int a, b, c;
}v[200002];

bool how(name A, name B)
{
    return (A.c < B.c);
}
int tata[200002], rang[200002];
struct
{
    int aa, bb;
}sol[200002];

int multime(int nod)
{
    int rad = nod;
    while (rad != tata[rad])
        rad = tata[rad];
    return rad;
}
void unite(int tatax, int tatay)
{
    if (rang[tatax] < rang[tatay])
        tata[tatax] = tatay;
    else
        tata[tatay] = tatax;
    if (rang[tatax] == rang[tatay])
        ++rang[tatax];
}
int main()
{
    f = fopen("apm.in", "r");
    g = fopen("apm.out", "w");
    int m, n, x, y, mx, my, ss = 0, cost = 0;
    fscanf(f, "%d %d", &n, &m);
    for (int i = 1;i <= m;++i)
        fscanf(f, "%d %d %d", &v[i].a, &v[i].b, &v[i].c);
    sort(v + 1, v + m + 1, how);
    for (int i = 1;i <= n;++i) tata[i] = i;
    for (int i = 1;i <= m;++i)
    {
        x = v[i].a;
        y = v[i].b;
        mx = multime(x);
        my = multime(y);
        if (mx != my)
        {
            unite(mx, my);
            cost += v[i].c;
            sol[++ss].aa = x;
            sol[ss].bb = y;
        }
    }
    fprintf(g, "%d\n%d\n", cost, ss);
    for (int i = 1;i <= n;++i)
        fprintf(g, "%d %d\n", sol[i].aa, sol[i].bb);

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