#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200010;

struct node {
    int from, to, dist;
};
int N, M;
vector<node> V;

int parent[MAXN];

bool comp(const node &a, const node &b) {
    return a.dist < b.dist;
}

void init() {
    for (int i = 1; i <= N;i++) parent[i] = i;
}

int root(int el) {
    if (parent[el] == el) return el;
    else {
        int tmp = root(parent[el]);
        parent[el] = tmp;
        return tmp;
    }
}

void join(int a, int b) {
    int rootA = root(a);
    int rootB = root(b);
    if (rootA != rootB) parent[rootB] = rootA;
}

vector<pair<int,int> > rs;
long long SUM = 0;

int main () {
    ifstream fin("apm.in");
    ofstream cout("apm.out");

    fin >> N >> M;
    init();
    for (int from, to, dist; M--;) {
        fin >> from >> to >> dist;
        V.push_back({from, to, dist});
    }
    sort(V.begin(), V.end(), comp);

    for (auto it: V) {
        if (root(it.from) != root(it.to)) {
            join(it.from, it.to);
            rs.push_back({it.from, it.to});
            SUM += it.dist;
        }
    }

    cout << SUM << endl << rs.size() << endl;
    for (auto it: rs) {
        cout << it.first << " " << it.second << endl;
    }

    return 0;
}