#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

const int NMAX = 200005;

int n, m;
vector<pair<int, pair<int,int>>> graph;
vector<pair<int, pair<int,int>>> tree;
int color[NMAX];

void initialize(int node) {
    color[node] = node;
}

void reunion(int i, int j) {
    for (int node = 1; node <= n; node++) {
        if (color[node] == color[j]) {
            color[node] = color[i];
        }
    }
}

bool comp(pair<int,int> p1, pair<int,int> p2) {
    return p1.second <= p2.second;
}

int main() {
    ifstream fin("grafpond.in");
    ofstream fout("grafpond.out");

    fin >> n >> m;
    int x, y, w;

    for (int i = 0; i < m; i++) {
        fin >> x >> y >> w;
        graph.emplace_back(w, make_pair(x, y));
    }

    sort(graph.begin(), graph.end());

    for (int node = 1; node <= n; node++) {
        initialize(node);
    }

    int nr = 0;
    int cost = 0;

    for (int i = 0; i < m; i++) {
        auto edge = graph[i].second;
        w = graph[i].first;
        x = edge.first;
        y = edge.second;
        if (color[x] != color[y]) {
            tree.emplace_back(w, make_pair(x, y));
            cost += w;

            reunion(x, y);
            nr++;

            if (nr == n - 1) {
                break;
            }
        }
    }

    cout << cost << "\n" << nr << "\n";
    for (auto edge : tree) {
        x = edge.second.first;
        y = edge.second.second;
        cout << x << " " << y << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}