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

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

const int maxM = 2e5 + 5;
const int maxN = 4e5 + 5;

struct muchie {
    int u, v, c;
}M[maxM];

vector <pair <int,int> > ans;
int t[maxN], rang[maxN];

bool comp (muchie a, muchie b) {
    if(a.c > b.c) return false;
    if(a.c < b.c) return true;
    if(a.u > b.u) return false;
    if(a.u < b.u) return true;
    if(a.v > b.v) return false;
    return true;
}

int radacina (int node) {
    if(t[node] == 0)
        return node;

    int root = radacina(t[node]);
    t[node] = root;

    return root;
}

int main() {

    int n, m; fin >> n >> m;

    for(int i = 1; i <= m; ++i)
        fin >> M[i].u >> M[i].v >> M[i].c;

    sort(M+1, M+m+1, comp);

    int apm = 0;
    for(int i = 1; i <= m; ++i) {
        int R1 = radacina(M[i].u);
        int R2 = radacina(M[i].v);
        if(R1 != R2) {

            apm += M[i].c;
            ans.push_back({M[i].u, M[i].v});

            if(rang[R1] < rang[R2]) {
                t[R1] = R2;
            } else {
                t[R1] = R2;
                if(rang[R1] == rang[R2])
                    rang[R2] += 1;
            }
        }
    }

    fout << apm << "\n" << ans.size() << "\n";
    for(auto i : ans)
        fout << i.first << " " << i.second << "\n";

    return 0;
}