#include <cstdio>
#include <algorithm>

using namespace std;

FILE *in, *out;

const int MAX_M = 400000, MAX_N = 100000;

int x[MAX_M], y[MAX_M], c[MAX_M], index[MAX_M];

int cost, mchii[MAX_N];

int n,m;

int apm[MAX_N];
int nr;

int t[MAX_N+1];

void init()
{
    for(int i = 0; i <= n; i++)
        t[i] = i;
}

int radacina(int x)
{
    if(t[x] == x) return x;
    t[x] = radacina(t[x]);
    return t[x];
}

void reuniune(int x, int y)
{
    t[radacina(x)] = radacina(y);
}

bool cmp(int i, int j)
{
    return (c[i] < c[j]);
}

int main()
{
    in = fopen("apm.in","r");
    out = fopen("apm.out", "w");

    fscanf(in,"%d%d", &n, &m);
    for(int i = 0; i < m; i++)
    {
        fscanf(in, "%d%d%d", x+i,y+i,c+i);
        index[i] = i;
    }
    init();
    sort(index, index+m, cmp);
    for(int i = 0; i < m; i++)
    {
        if(radacina(x[index[i]]) != radacina(y[index[i]]))
        {
            cost += c[index[i]];
            reuniune(x[index[i]], y[index[i]]);
            apm[nr++] = index[i];
        }
    }
    fprintf(out, "%d\n%d\n", cost, nr);
    for(int i = 0; i < n; i++)
        fprintf(out, "%d %d\n", x[apm[i]], y[apm[i]]);
    fcloseall();
    return 0;
}