#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
struct ura{
int x, y, c;}v[200001];
int sol[200001];
int t[200001];
bool cmp(ura a, ura b) {
    return a.c<b.c;
}
int sefsup(int x) {
   if(x==t[x]) {
    return x;
   }
   else {
    return t[x]=sefsup(t[x]);
   }
}
void unire(int x, int y) {
   int sefx=sefsup(x);
   int sefy=sefsup(y);
   t[sefy]=sefx;

}

int main() {
    int i, n, m, k;

    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].c;
    }
    sort(v+1, v+m+1, cmp);
    k=0;
    for(i=1;i<=n;i++) {
        t[i]=i;
    }
    int cost=0;
    for(i=1;i<=m;i++) {
        if(sefsup(v[i].x)!=sefsup(v[i].y) && k<n-1) {
            k++;
            cost=cost+v[i].c;
            sol[k]=i;
            unire(v[i].x, v[i].y);
        }
    }
    fout<<cost<<"\n"<<n-1<<"\n";
    for(i=1;i<=n-1;i++) {
        fout<<v[sol[i]].x<<" "<<v[sol[i]].y<<"\n";
    }
    return 0;
}