#include <bits/stdc++.h>
using namespace std;
#define NMAX 100001
int tati[NMAX];
int h[NMAX];
ifstream fin ("apm.in");
ofstream fout ("apm.out");
int Find(int x) {
    int rad=x;
    while(tati[rad]!=0)
        rad = tati[rad];

    // compresia
    // cand trece face fiecare nod sa aiba radacina rad => face drumul de lungime 1 data viitoare
    while(tati[x]) {
        int tx=tati[x];
        tati[x]=rad;
        x=tx;
    }

    return rad;
}
void Union(int x, int y) {
    int arx = Find(x), ary = Find(y);
    if (arx == ary) return;

    // facem inaltimea minima
    // arx este mai mic => aceeasi inaltime maxima
    // arx == ary => inaltime maxima +1
    if (h[arx] <= h[ary])
        tati[arx] = ary;
    // ary este mai mare
    else tati[ary] = arx;
}
struct muchie {
    int x=0,y=0,cost=0;
    friend const bool operator > (muchie a, muchie b) {
        return a.cost > b.cost || ( a.cost == b.cost && a.x > b.x);
    }
} tempmuchie;
vector<muchie> sel;
int main() {
    int cost,n,m;
    fin>>n>>m;
    // Asa se face min-heap in loc de max-heap pt ca priority_queue este max-heap
    priority_queue<muchie, vector<muchie>, greater<muchie>> q;
    for(int i=1; i<=m; i++) {
        fin>>tempmuchie.x>>tempmuchie.y>>tempmuchie.cost;
        q.push(tempmuchie);
    }
    cost = 0;
    while(!q.empty()) {
        tempmuchie = q.top();
        int arx = Find(tempmuchie.x), ary = Find(tempmuchie.y);
        if(arx!=ary) {
            sel.push_back(tempmuchie);
            cost += tempmuchie.cost;
            Union(arx, ary);
        }
        q.pop();
    }
    fout<<cost<<'\n';
    fout<<sel.size()<<'\n';
    for(int i=0; i<sel.size(); i++)
        fout<<sel[i].y<<' '<<sel[i].x<<'\n';
    return 0;
}