#include <algorithm>
#include <fstream>
#define NMAX 200005
#define MMAX 400005

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m;
int v[NMAX], nr[NMAX];
int cost, cnt;

struct muchie
{
    int start, finish;
    int cost;
}drum[MMAX];

muchie sol[MMAX];

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

// union-find

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

void reunion(int x, int y)
{int sol[MMAX];
    int rx = radacina(x);
    int ry = radacina(y);
    if (nr[ry] < nr[rx]) {
        v[ry] = rx;
        nr[rx] += nr[ry];
    }
    else {
        v[rx] = ry;
        nr[ry] += nr[rx];
    }
}

bool verifica(int x, int y)
{
    return radacina(x) == radacina(y);
}

int main()
{
    fin>>n>>m;
    for (int i = 1; i <= m; i++) {
        fin>>drum[i].start>>drum[i].finish>>drum[i].cost;
    }
    sort(drum + 1, drum + m + 1, cmp);
    for (int i = 1; i <= m; i++) {
        if (!verifica(drum[i].start, drum[i].finish)) {
            sol[++cnt].start = drum[i].start;
            sol[cnt].finish = drum[i].finish;
            sol[cnt].cost = sol[cnt - 1].cost + drum[i].cost;
            reunion(drum[i].start, drum[i].finish);
        }
    }
    fout<<sol[cnt].cost<<'\n'<<cnt<<'\n';
    for (int i = 1; i <= cnt; i++) {
        fout<<sol[i].start<<' '<<sol[i].finish<<'\n';
    }
}