#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>


using namespace std;

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


struct muchie{
    int x,y,cost;
};

int n,m,c; int poz[400005]; muchie a[400005]; int r[200005]; vector <int> sol;

bool comp(int i,int j) {
    return (a[i].cost < a[j].cost);
}

int rad(int x) {
    int rr = x; int aux;
    while(r[x] != rr) {
        rr = r[x];
    }
    while(x != rr) {
        aux = r[x];
        r[x] = rr;
        x = aux;
    }
    return rr;
}

void unite(int x,int y) {
    r[rad(x)] = rad(y);
}

int main() {
    int i;
    f>>n>>m;
    for(i = 1; i <= m; ++i) {
        f>>a[i].x>>a[i].y>>a[i].cost;
        poz[i] = i;
    }
    for(i = 1; i <= n; ++i) {
        r[i] = i;
    }
    sort(poz+1,poz+m+1,comp);
    for(i = 1; i <= m; ++i) {
        if(rad(a[poz[i]].x != rad(a[poz[i]].y))) {
            c += a[poz[i]].cost;
            unite(a[poz[i]].x,a[poz[i]].y);
            sol.push_back(poz[i]);
        }
    }
    g<<c<<'\n';
    g<<n-1<<'\n';
    --n;
    for(i = 0; i < n; ++i) {
        g<<a[sol[i]].x<<' '<<a[sol[i]].y;
    }
    return 0;
}