#include<iostream>
#include<fstream>
#include<list>
#include<queue>
#include<limits>
using namespace std;
typedef pair<int, int> pereche;

#define INF std::numeric_limits<int>::max()
//Pentru infinit folosim valoarea maxima a unui integer

int n,m;
class Graf{
    int muchii;
    list< pereche > *vecini;

public:
    Graf(int muchii);
    void addMuchie(int a, int b, int g);
    void PrimsAlg();
};

Graf::Graf(int muchii){
    this->muchii = muchii;
    vecini = new list< pereche > [muchii];
}

void Graf::addMuchie(int a, int b, int g){
    vecini[a].push_back(make_pair(b, g));
    vecini[b].push_back(make_pair(a, g));
}

void Graf::PrimsAlg(){
    priority_queue< pereche, vector<pereche>, greater<pereche> > coada;

    int radacina = 0;
    int costTotal = 0, nrNoduri = 0;
    vector<int> key(muchii, INF);
    vector<int> parinti(muchii, -1);
    vector<bool> vizitat(muchii, false);

    coada.push(make_pair(0, radacina));
    key[radacina] = 0;

    while(!coada.empty()){
        int u = coada.top().second;
        coada.pop();
        vizitat[u] = true;

        list< pereche >::iterator i;
        for(i = vecini[u].begin(); i!= vecini[u].end(); ++i){
            int v = (*i).first;
            int greutate = (*i).second;
            if(vizitat[v] == false && key[v] > greutate){
                costTotal -= key[v];
                key[v] = greutate;
                costTotal += key[v];
                coada.push(make_pair(key[v], v));
                parinti[v] = u;
            }
        }
    }
    nrNoduri = n-1;
    ofstream fout;
    fout.open("apm.out");
    fout<<costTotal-nrNoduri<<endl<<nrNoduri<<endl;
    for(int i = 1; i <= nrNoduri ; ++i){
        fout<<parinti[i]+1<<" "<<i+1<<endl;
    }
}
int main(){
    ifstream fin;
    fin.open("apm.in");
    fin>>n>>m;

    Graf g(m);
    for(int i=0;i<m;i++){
        int a,b,gr;
        fin>>a>>b>>gr;
        g.addMuchie(a-1,b-1,gr);
    }
    g.PrimsAlg();

}