#include <fstream>
#define NMAX 400010
#include <algorithm>
using namespace std;
struct muchie {int cost,x,y;};
muchie a[NMAX],sol[NMAX];
int R[NMAX],T[NMAX],i,j,k,NR,n,m,c,sum;
bool cmp(muchie a, muchie b)
{
    if (a.cost==b.cost)
       {
           if (a.x==b.x) return a.y<b.y;
           return a.x<b.x;
       }
    return a.cost<b.cost;
}
int multime(int nod) {
    if (T[nod]!=nod)
        T[nod]=multime(T[nod]);
    return T[nod];
}
void reuneste(int i,int j) {
    i=multime(i);
    j=multime(j);
    if (i==j) return;
    if (R[i]<R[j])
        T[i]=j;
    else
        T[j]=i;
    if (R[i]==R[j])
        R[i]++;
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for (i=1;i<=m;i++)
       f>>a[i].x>>a[i].y>>a[i].cost;
    sort(a+1,a+m+1,cmp);
    for (i=1; i<=n; i++) {
        T[i]=i;
        R[i]=0;
    }
    for (i=1; i<=m; i++) {
        j=a[i].x;
        k=a[i].y;
        c=a[i].cost;
        if (multime(i)!=multime(j)) {
            reuneste(i,j);
            sum+=c;
            sol[++NR].x=j;
            sol[NR].y=k;
        }
    }
    g<<sum<<'\n'<<NR<<'\n';
    for (i=1; i<=NR; i++)
        g<<sol[i].x<<" "<<sol[i].y<<'\n';
    f.close();
    g.close();
    return 0;
}