#include <bits/stdc++.h>

#define NMAX 100005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int N, M;
int t[NMAX];

// 1 2 3 4 5 6 7 8 9
// 1 1 2 2 1 6 6 6 7
int find(int nod) {
    if (t[nod] == nod)
        return nod;
    return (t[nod] = find(t[nod]));
}

void unite(int nod1, int nod2) {
    int r1 = find(nod1);
    int r2 = find(nod2);
    t[r2] = r1;
}

struct edge {
    int x, y;
    int c;
};

void read();

vector<edge> v;

bool cmp(edge A, edge B) {
    return (A.c < B.c);
}

vector<pair<int, int>> sol;

int main() {
    read();
    sort(v.begin(), v.end(), cmp);
    int s = 0;
    for (auto it: v) {
        int r1 = find(it.x);
        int r2 = find(it.y);
        if (r1 == r2)
            continue;
        else {
            unite(it.x, it.y);
            sol.emplace_back(it.x, it.y);
            s += it.c;
        }
    }
    fout << s << '\n';
    fout << N - 1 << '\n';
    for (auto it: sol)
        fout << it.first << ' ' << it.second << '\n';
    return 0;
}

void read() {
    fin >> N >> M;
    for (int i = 1; i <= N; i++)
        t[i] = i;
    for (int i = 1; i <= M; i++) {
        edge A;
        fin >> A.x >> A.y >> A.c;
        v.push_back(A);
    }
}