#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
#define dim 8192
int pz;
char ax[dim];
struct muchie {
    int x, y, c;
} v[400001];
int cmp(muchie a, muchie b) {
    if (a.c < b.c) return 1;
    return 0;
}
void cit(int &x) {
    int ok = 0;
    x = 0;
    while ((ax[pz] < '0' || ax[pz] > '9') && ax[pz] != '-')
        if (++pz == dim) f.read(ax,dim), pz = 0;
    if (ax[pz] == '-') ok = 1, ++pz;
    if (pz == dim) f.read(ax,dim), pz = 0;
    while (ax[pz] >= '0' && ax[pz] <= '9') {
        x = x * 10 + ax[pz] - '0';
        if (++pz == dim) f.read(ax,dim), pz = 0;
    }
    if (ok) x = x * -1;
}
int n, m, x, y, c, t[200001], cost;
int find(int i) {
    if (t[i] != i) t[i] = find(t[i]);
    return t[i];
}
void uneste(int i, int j) {
    i = find(i);
    j = find(j);
    if (i == j) return;
    t[i] = j;
}
int main()
{
    vector<int> sol;
    cit(n), cit(m);
    for (int i = 1; i <= m; ++i) cit(v[i].x), cit(v[i].y), cit(v[i].c);
    sort(v+1, v+m+1, cmp);
    for (int i = 1; i <= n; ++i) t[i] = i;
    int j = 1;
    for (int i = 1; i < n; ++i) {
        while (find(v[j].x) == find(v[j].y)) ++j;
        uneste(v[j].x,v[j].y);
        sol.push_back(j);
        cost += v[j].c;
    }
    g << cost << '\n' << sol.size() << '\n';;
    for (int i = 0; i < sol.size(); ++i) g << v[sol[i]].x << ' ' << v[sol[i]].y << '\n';
    return 0;
}