#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int MAX_NUM = 400005;

int n, m;
int parent[MAX_NUM], x[MAX_NUM], y[MAX_NUM], cost[MAX_NUM];
vector<int> edgeIndex(MAX_NUM);

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

void unify(int i, int j) {
    parent[find(j)] = find(i);
}

bool sortCrt(int i, int j) {
    return cost[i] < cost[j];
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        fin >> x[i] >> y[i] >> cost[i];
        edgeIndex[i] = i;
    }
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }
    sort(edgeIndex.begin() + 1, edgeIndex.begin() + m + 1, sortCrt);
    int answer = 0;
    vector<int> solutions;
    for (int i = 1; i <= m; ++i) {
        int u = x[edgeIndex[i]];
        int v = y[edgeIndex[i]];
        if (find(u) != find(v)) {
            answer += cost[edgeIndex[i]];
            unify(u, v);
            solutions.push_back(edgeIndex[i]);
        }
    }
    fout << answer << "\n";
    fout << solutions.size() << "\n";
    for (int i = 0; i < solutions.size(); ++i) {
        fout << x[solutions[i]] << " " << y[solutions[i]] << "\n";
    }
    return 0;
}