#include <bits/stdc++.h>
#define NMAX 500005

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int N, M, K, cnt, totalCost, parent[NMAX];
struct asd {
    int x, y, c;
};

vector < asd > edge;
vector < int > res;

bool cmp(const asd &A, const asd &B) {
    return (A.c < B.c);
}

int _find(int node) {
    if (parent[node] != node) {
        parent[node] = _find(parent[node]);
    }

    return parent[node];
}

void unite(int x, int y) {
    parent[_find(x)] = _find(y);
}

int main() {
    f >> N >> M;
    edge.resize(M);
    K = N - 1;

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

    for (int i = 0; i < M; ++i) {
        f >> edge[i].x >> edge[i].y >> edge[i].c;
    }

    sort(edge.begin(), edge.end(), cmp);
    for (int i = 0; i < M && cnt <= K; ++i) {
        if (_find(edge[i].x) != _find(edge[i].y)) {
            unite(edge[i].x, edge[i].y);
            totalCost += edge[i].c;
            res.push_back(i);
            ++cnt;
        }
    }

    g << totalCost << '\n' << cnt << '\n';
    for (auto it : res) {
        g << edge[it].x << ' ' << edge[it].y << '\n';
    }
    return 0;
}