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

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

const int nmax = 200005; 

struct muchie {
    int x, y, c, id; 
} v[400005];

int parent[nmax];
int Rang[nmax];
int n, m, Cost;
vector<pair<int, int>> solutie; 

int find(int x) {
    int nod, y;
    for (nod = x; parent[nod] != nod; nod = parent[nod]);
    while (parent[x] != x) {
        y = parent[x];
        parent[x] = nod;
        x = y;
    }
    return nod;
}

bool mrg(int n1, int n2) {
    int r1 = find(n1), r2 = find(n2);
    if (r1 == r2)
        return false;

    if (Rang[r1] > Rang[r2])
        parent[r2] = r1;
    else {
        parent[r1] = r2;
        if (Rang[r1] == Rang[r2])
            Rang[r2]++;
    }
    return true;
}

bool cmp(muchie a, muchie b) {
    return a.c < b.c;
}

int main() {
    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        f >> v[i].x >> v[i].y >> v[i].c;
    }

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

    sort(v + 1, v + m + 1, cmp);

    for (int i = 1; i <= m; i++) {
        if (mrg(v[i].x, v[i].y)) {
            Cost += v[i].c;
            solutie.push_back({v[i].x, v[i].y});
        }
    }

  
    g << Cost << "\n";
    g << n - 1 << "\n";
    for (auto p : solutie) {
        g << p.first << " " << p.second << "\n";
    }

    return 0;
}