#include <fstream>
#include <algorithm>
#include <vector>
const int NMAX = 400001;
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int t[NMAX], N, M, rez, l[NMAX];
struct muchie {
    int x, y, c;
} v[NMAX];
vector<int> v2;

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

int find(int i) {
    if(t[i] == i) return i;
    return t[i] = find(t[i]);;
}

void uni(int i, int j) {
    t[find(i)] = find(j);
}

int main()
{
    f >> N >> M;
    for(int i = 1; i <= M; ++i) {
        f >> v[i].x >> v[i].y >> v[i].c;
        l[i] = i;
    }
    for(int i = 1; i <= N; ++i)
        t[i] = i;
    sort(l + 1, l + M + 1, cmp);
    for(int i = 1; i <= M; ++i) {
        if(find(v[l[i]].x) != find(v[l[i]].y)) {
            rez += v[l[i]].c;
            uni(v[l[i]].x, v[l[i]].y);
            v2.push_back(l[i]);
        }
    }

    g << rez << '\n' << N - 1 << '\n';
    for(int i = 0; i < N - 1; ++i)
        g << v[v2[i]].y << ' ' << v[v2[i]].x << '\n';

    f.close();
    g.close();
    return 0;
}