#include <fstream>
#include <algorithm>
#define DIMN 200010
#define DIMM 400010
using namespace std;

struct muchie {
    int x;
    int y;
    int cost;
};
muchie v[DIMM];
int n,m,i,radx,rady,k,sol;
int s[DIMN],t[DIMN];
int rad (int x){
    while (t[x] > 0)
        x = t[x];
    return x;
}
int cmp (muchie a,muchie b){
    return a.cost < b.cost;
}


int main (){

    ifstream fin ("apm.in");
    ofstream fout ("apm.out");
    fin>>n>>m;
    for (i=1;i<=m;i++)
        fin>>v[i].x>>v[i].y>>v[i].cost;
    sort (v+1,v+m+1,cmp);
    for (i=1;i<=n;i++)
        t[i] = -1;
    for (i=1;i<=m;i++){
        radx = rad (v[i].x);
        rady = rad (v[i].y);
        if (radx != rady){
            sol += v[i].cost;
            s[++k] = i;
            if (t[radx] < t[rady]){
                t[radx] += t[rady];
                t[rady] = radx;
            }
            else{
                t[rady] += t[radx];
                t[radx] = rady;
            }

        }
    }
    fout<<sol<<"\n"<<n-1<<"\n";
    for (i=1;i<n;i++)
        fout<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";

    return 0;
}