#include <iostream>
#include <fstream>
#include <algorithm>

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

// KRUSKAL

const int mMax = 4e5, nMax = 2e5;

typedef struct {
    unsigned int u, v;
    short cost;
} Muchie;

std::pair<int, int> p[mMax];
int k;

int N, M, total, tt[nMax], rg[nMax];

Muchie muchii[mMax];

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

void read() {
    fin >> N >> M;

    for(int i = 0; i < M; ++i) {
	fin >> muchii[i].u >> muchii[i].v >> muchii[i].cost;
	muchii[i].u--, muchii[i].v--;
    }

    std::sort(muchii, muchii + M, cmp);

    for(int i = 0; i < N; ++i)
	tt[i] = i, rg[i] = 1;
}

int radacina(int nod) {
    while(tt[nod] != nod)
	nod = tt[nod];
    return nod;
}

void unire(int u, int v) {
    if(rg[u] < rg[v])
	tt[u] = v;
    else if(rg[u] > rg[v])
	tt[v] = u;
    else {
	tt[u] = v;
	rg[v]++;
    }
}

void rezolvare() {
    for(int i = 0; i < M; ++i) {
	int tu = radacina(muchii[i].u), tv = radacina(muchii[i].v);
	if(tu != tv) {
	    unire(tu, tv);

	    p[k].first = muchii[i].u;
	    p[k++].second = muchii[i].v;
	    total += muchii[i].cost;
	}
    }
}

void afisare() {
    fout << total << '\n' << N-1 << '\n';
    for(int i = 0; i < k; ++i)
	fout << p[i].first + 1 << ' ' << p[i].second + 1 << '\n';
}

int main() {
    read();
    rezolvare();
    afisare();

    fin.close();
    fout.close();
    return 0;
}