#include <iostream>
#include <vector>
#include <set>
#include <fstream>
#define infinit 1<<30
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct nodd{
int nod;
int cost;
};
struct lex_compare {
    bool operator() (const nodd& lhs, const nodd& rhs) const {
        return lhs.cost < rhs.cost ;
    }
};
int main()
{
    int n, x, y, cost, m, radacina, costminim = 0, *costuri, k=0;
    fin >> n >> m;
    int *tata;
    nodd tmp;
    tata = new int[n+1];
    costuri = new int[n+1]();
    multiset<nodd, lex_compare> costNod;
    vector<nodd> costMuchii[n+1];
    for ( int i = 1 ; i <= m ; i++ ){
        fin >> x >> y >> cost ;
        tmp.nod = y ;
        tmp.cost = cost ;
        costMuchii[x].push_back(tmp) ;
        tmp.nod = x ;
        costMuchii[y].push_back(tmp) ;

    }
    radacina = 1;
    tmp.nod = radacina;
    tmp.cost = 0;
    costNod.insert(tmp);
    tmp.cost = infinit;
    for( int i = 1 ; i <= n ; i++ ){
        tmp.nod = i;
        tata[i] = 0;
        if(i != radacina)
        costNod.insert(tmp);
    }
    while(!costNod.empty()){
        costNod.erase(costNod.begin());
        for ( vector<nodd> :: iterator it = costMuchii[radacina].begin() ; it != costMuchii[radacina].end() ; ++it){
            for ( set<nodd> :: iterator it1 = costNod.begin() ; it1 != costNod.end() ; it1++){
                if(it->nod == it1->nod && it->cost < it1->cost){
                    tata[it->nod] = radacina;
                    costNod.erase(it1);
                    tmp.cost = it->cost;
                    tmp.nod = it->nod;
                    costNod.insert(tmp);
                    costuri[it->nod] = it->cost;
                    break;
                }
            }
        }
        radacina = costNod.begin()->nod;

    }
    for(int i = 1 ; i <= n ; i++){
        costminim += costuri[i];
        for(int j = 1 ; j <= n ; j++){
            if(tata[j]==i)
            k++;
            //cout<<i<<' '<<j<<endl;
        }
    }
    fout<<costminim<<endl<<k<<endl;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j++){
            if(tata[j]==i)
            fout<<i<<' '<<j<<endl;
        }
    }

    return 0;
}