#include <fstream>
#include <vector>
#include <queue>
#include <iostream>
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];
	}
	static 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];
	}
	bool operator>(const triple&)const ;
};

bool triple:: operator>(const triple& c) const{
	if(a[0]<c.a[0]) return false;
	if(a[0]>c.a[0]) return true;
	if(a[1]<c.a[1]) return false;
	if(a[1]>c.a[1]) return true;
	if(a[2]<c.a[2]) return false;
	return true;
}
template<class T>
struct greater1 : binary_function <T,T,bool> {
	  bool operator() (const T& x, const T& y) const {return x>y;}
};
vector<bool> viz;
vector< vector< pair<int,int> > > vecini;
vector< pair<int,int> > sol;
priority_queue< triple, vector< triple >, greater1<triple> > Q;

int main() {
    ifstream in("apm.in");
    int n,m,x,y,z,cost=0;
    in>>n>>m;
	vecini.assign(n+1,sol);
	viz.assign(n+1,false);
    for(register int i=0; i<m; i++) {
        in>>x>>y>>z;
        vecini[x].push_back(make_pair(y,z));
        vecini[y].push_back(make_pair(x,z));
    }
    viz[1] = true;
    for(register unsigned  i=0; i<vecini[1].size(); i++ )
        Q.push(triple::make_triple(vecini[1][i].second, 1, vecini[1][i].first));
	
	triple aux;
    for(;!Q.empty();) {
        aux = Q.top(); Q.pop();
        if (!viz[aux.get(2)]) {
            cost += aux.get(0);
            viz[aux.get(2)] = true;
            sol.push_back( make_pair(aux.get(1),aux.get(2)) );
            for (unsigned i=0; i< vecini[aux.get(2)].size(); i++)
                if (!viz[vecini[aux.get(2)][i].first])
                    Q.push(triple::make_triple(vecini[aux.get(2)][i].second, aux.get(2), vecini[aux.get(2)][i].first ) );
        }
    }
	ofstream out("apm.out");
    out<<cost<<'\n'<<sol.size()<<'\n';
    for (register unsigned i=0; i<sol.size();i++)
        out<<sol[i].first<<' '<<sol[i].second<<'\n';
	out.close();
    return 0;
}