#include<vector>
#include<fstream>
#include<queue>
#include<algorithm>
using namespace std;

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

struct muchie {
    int a,b,c,fol;
};

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

int n,m,v[200101],nr1,nr2,cost,nr=1;
muchie l[401001],l1[401001];

inline bool ver(const int &a,const int &b) {

    nr1=a;
    nr2=b;

    while(v[nr1])
        nr1=v[nr1];

    while(v[nr2])
        nr2=v[nr2];

    if(nr1!=nr2)
        return 1;
    return 0;

}

inline void kruskal() {
    int i;

    for(i=1;i!=n;++i) {

        while(!ver(l1[nr].a,l1[nr].b))
              ++nr;

        l[l1[nr].fol].fol=0;
        cost+=l1[nr].c;


        v[nr2]=nr1;


    }
}

int main() {
	int i;

	in >> n >> m;

	for(i=1;i<=m;++i) {
        in >> l[i].a >> l[i].b >> l[i].c;
        l[i].fol=i;

        l1[i]=l[i];
	}

    sort(&l1[1],&l1[m+1],cmp);

    for(i=1;i<=n;++i)
        v[i]=0;

    kruskal();

    out << cost << "\n" << n-1 << "\n";

    for(i=1;i<=m;++i)
        if(!l[i].fol)
            out << l[i].a << " " << l[i].b << "\n";

	return 0;
}