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

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

const int maxn = 2e5 + 5;
const int maxm = 4e5 + 5;

class Edge {
public:
    int x, y, cost;
    inline bool operator () (const Edge& A, const Edge& B) {
        return A.cost < B.cost;
    }
};

Edge G[maxm];
pair <int,int> Apm[maxn];
int n, m, lg, Dad[maxn], Rang[maxn];

int Find (int node) {
    while (node != Dad[node]) {
        node = Dad[node];
    }
    return node;
}

void Union (int x, int y) {
    if (Rang[x] > Rang[y]) {
        Dad[y] = x;
    } else {
        Dad[x] = y;
    }
    if (Rang[x] == Rang[y]) Rang[y]++;
}

int Kruskal () {
    int i, rx, ry, min_cost = 0;
    for (i = 1; i <= n; i++) {
        Dad[i] = i;
    }
    sort(G + 1, G + m + 1, Edge());
    for (i = 1; i <= m; i++) {
        rx = Find(G[i].x);
        ry = Find(G[i].y);
        if (rx != ry) {
            min_cost += G[i].cost;
            Apm[++lg] = make_pair(G[i].x, G[i].y);
            Union(rx, ry);
        }
    }
    return min_cost;
}

int main() {
    ios_base :: sync_with_stdio (false);
    int i;
    fin >> n >> m;
    for (i = 1; i <= m; i++) {
        fin >> G[i].x >> G[i].y >> G[i].cost;
    }
    fout << Kruskal() << "\n" << n - 1 << "\n";
    for (i = 1; i < n; i++) {
        fout << Apm[i].first << " " << Apm[i].second << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}