#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 200005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{
    int x, y, cost;
};
int N, M;
vector<muchie> v, ans;
int t[NMAX], r[NMAX];
void read() {
    fin >> N >> M;
    muchie x;
    for (int i = 0; i < M; ++i) {
        fin >> x.x >> x.y >> x.cost;
        v.push_back(x);
    }
}
bool comp(muchie m1, muchie m2) {
    if (m1.cost == m2.cost) {
        if (m1.x == m2.x) {
            return m1.y < m2.y;
        }
        return m1.x < m2.x;
    }
    return m1.cost < m2.cost;
}
int findRoot(int x) {
    if (x == t[x]) {
        return x;
    }
    t[x] = findRoot(t[x]);
    return t[x];
}
void mergeSets(int x, int y) {
    x = findRoot(x);
    y = findRoot(y);
    if (r[x] < r[y]) {
        swap(x, y);
    }
    if (r[x] == r[y]) {
        ++r[x];
    }
    t[y] = x;
}
int main()
{
    read();
    sort(v.begin(), v.end(), comp);
    for (int i = 1; i <= N; ++i) {
        t[i] = i;
    }
    int sum = 0;
    for (int i = 0; i < M; ++i) {
        if (findRoot(v[i].x) != findRoot(v[i].y)) {
            mergeSets(v[i].x, v[i].y);
            sum += v[i].cost;
            ans.push_back(v[i]);
        }

    }
    fout << sum << "\n" << ans.size() << "\n";
    for (int i = 0; i < ans.size(); ++i) {
        fout << ans[i].x << " " << ans[i].y << "\n";
    }
    return 0;
}