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

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

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

class cmp {
public:
    bool operator() (muchie a, muchie b) {
        return a.c>b.c;
    }
};

int n,m,v[200101],nr1,nr2,cost;
muchie l[401001];
priority_queue<muchie, vector<muchie>, cmp> h;

bool ver(int a,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;

}

void kruskal() {
    int i;

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

        while(!ver(h.top().a,h.top().b))
              h.pop();

        l[h.top().fol].fol=0;
        cost+=h.top().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;

        h.push(l[i]);
	}

    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;
}