#include<fstream>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class triple{
	int a[3];
public:
	triple(int x=0, int y=0, int z=0){
		a[0]=x; a[1]=y; a[2]=z;
	}
	triple(const triple& ac){
		a[0]=ac.a[0]; a[1]=ac.a[1]; a[2]=ac.a[2];
	}
	triple make_triple(int x=0, int y=0, int z=0){
		triple r(x,y,z);
		return r;
	}
	int& get(int x){
		return a[x];
	}
	friend istream& operator>>(istream&, triple&);
	friend ostream& operator<<(ostream&, triple&);
	bool operator<(const triple&)const ;
};
istream& operator>>(istream& in, triple& ac){
	in>>ac.a[1]>>ac.a[2]>>ac.a[0];
	return in;
}
ostream& operator<<(ostream& out, triple& ac){
	out<<ac.a[1]<<' '<<ac.a[2];
	return out;
}
bool triple:: operator<(const triple& c) const{
	if(a[0]<c.a[0]) return true;
	if(a[0]>c.a[0]) return false;
	if(a[1]<c.a[1]) return true;
	if(a[1]>c.a[1]) return false;
	if(a[2]<c.a[2]) return true;
	return false;
}		
vector<int> b;
int un(int x) {
    if(b[x]==x) return x;
    b[x] = un( b[x] );
    return b[x];
}
int main () {
	int n,m,cost;
	vector< triple > arbore, sol; 
	triple aux;
    ifstream in("apm.in");
    in>>n>>m;
    for(int i=0;i<m;++i) {
		in>>aux; arbore.push_back(aux);
	}
	in.close();
    sort(arbore.begin(),arbore.end());
    for(int i=0;i<n+1;++i) b.push_back(i);
    for(int i=0;i<m;++i) {
		int x = un(arbore[i].get(1)), y = un(arbore[i].get(2));
        if( x != y) {
            b[x]=y;
            sol.push_back(arbore[i]);
            cost+=arbore[i].get(0);
        }
    }
    ofstream out("apm.out");
	out<<cost<<'\n'<<sol.size()<<'\n';
	for(unsigned i=0; i<sol.size(); i++)
		out<<sol[i]<<'\n';
	out.close();
    return 0;
}