#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

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

int find_boss(int x, vector<int> & boss) {
    if (boss[x] == x) {
        return x;
    }
    boss[x] = find_boss(boss[x], boss);
    return boss[x];
}

void unite(int x, int y, vector<int> & boss, vector<int> & height) {
    int boss_x = find_boss(x, boss);
    int boss_y = find_boss(y, boss);
    if (height[boss_x] > height[boss_y]) {
        boss[boss_y] = boss[boss_x];
    } else {
        boss[boss_x] = boss[boss_y];
        if (height[boss_x] == height[boss_y]) {
            ++height[boss_y];
        }
    }
}

int main() {
    FILE * f;
    int n, m;

    f = fopen("apm.in", "r");
    fscanf(f, "%d%d", &n, &m);
    vector<edge> edges(m);
    for (int i = 0; i < m; ++i) {
        fscanf(f, "%d%d%d", &edges[i].x, &edges[i].y, &edges[i].c);
    }
    fclose(f);

    sort(edges.begin(), edges.end(), [](edge a, edge b) {return a.c < b.c;});

    vector<int> boss(n + 1);
    vector<int> height(n + 1);
    for (int i = 1; i <= n; i++) {
        boss[i] = i;
        height[i] = 1;
    }

    vector<pair<int, int> > apm;
    int total_cost = 0;
    for (int i = 0; i < m; ++i) {
        if (find_boss(edges[i].x, boss) != find_boss(edges[i].y, boss)) {
            total_cost += edges[i].c;
            unite(edges[i].x, edges[i].y, boss, height);
            apm.push_back({edges[i].x, edges[i].y});
        }
    }

    f = fopen("apm.out", "w");
    fprintf(f, "%d\n%d\n", total_cost, n - 1);
    for (int i = 0; i < n - 1; ++i) {
        fprintf(f, "%d %d\n", apm[i].first, apm[i].second);
    }
    fclose(f);

    return 0;
}