#include <fstream>
#include <algorithm>

using namespace std;
const int nmax = 200005;

struct node{
    int a, b, cost;
};
bool comp(node a, node b){
    return a.cost < b.cost;
}
int father[nmax];
int x[nmax], y[nmax];
int cost_total;
node l[nmax];
int n, m;

int find(int nod){
    if(father[nod] < 0){
        return nod;
    }
    int tata = find(father[nod]);
    father[nod] = tata;
    return tata;
}
void unite(int x, int y){
    if(father[x] < father[y]){
        swap(x, y);
    }
    father[y] += father[x];
    father[x] = y;
}
int main(){
    ifstream f("apm.in");
    ofstream g("apm.out");
    f >> n >> m;
    int cnt = 0;
    for(int i = 1; i <= m; i++){
        f >> l[i].a >> l[i].b >> l[i].cost;
    }
    for(int i = 1; i <= n; i++){
        father[i] = -1;
    }
    sort(l + 1, l + m + 1, comp);
    for(int i = 1; i <= m; i++){
        int r_a = find(l[i].a);
        int r_b = find(l[i].b);
        if(r_a != r_b){
            cnt++;
            x[cnt] = l[i].a;
            y[cnt] = l[i].b;
            cost_total += l[i].cost;
            unite(r_a, r_b);
        }
    }
    g << cost_total << '\n' << cnt << '\n';
    for(int i = 1; i <= n; i++){
        g << x[i] << ' ' << y[i] << '\n';
    }
}