#include <fstream>
#include <algorithm>
#define n_max 200002

using namespace std;

ifstream r("apm.in");
ofstream w("apm.out");

pair <int,int>sol[n_max];
struct muchie {
    int x,y,c;
} v[2*n_max];
int tata[n_max],rg[n_max],m,n,k,cost;

bool comp(muchie a, muchie b) {
    return a.c<b.c;
}

int radacina(int nod) {
    if (tata[nod]==0)
        return nod;
    else {
        tata[nod]=radacina(tata[nod]);
        return tata[nod];
    }
}

void read() {
    int i;
    r>>n>>m;
    for (i=1; i<=m; i++)
        r>>v[i].x>>v[i].y>>v[i].c;
}

void solve() {
    int i,tx,ty;
    for (i=1; i<=n; i++)
        rg[i]=1;
    for (i=1; i<=m; i++) {
        tx=radacina(v[i].x);
        ty=radacina(v[i].y);
        if (tx!=ty) {
            if (rg[tx]>rg[ty])
                tata[ty]=tx;
            else
                tata[tx]=ty;
            if (rg[tx]==rg[ty])
                    rg[ty]++;
            k++;
            sol[k].first=v[i].x;
            sol[k].second=v[i].y;
            cost+=v[i].c;
        }
    }
}

int main() {
  read();
  sort(v+1,v+m+1,comp);
  solve();
  w<<cost<<"\n"<<n-1<<"\n";
  for (int i=1; i<=k; i++)
    w<<sol[i].first<<" "<<sol[i].second<<"\n";
  r.close();
  w.close();
  return 0;
}