#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

struct Muchie{
    int x,y;
    int cost;

    bool operator<(const Muchie& obj){
        return this->cost<obj.cost;
    }
};

int Reprez(int u, vector<int>& tata){ //intoarcem reprezentantul subarborelui
    if(tata[u]==0)
        return u;
    tata[u]=Reprez(tata[u],tata); //compresie de cale
    return tata[u];
}

void Reuneste(int u, int v, vector<int>& tata, vector<int>& h){
    int ru = Reprez(u,tata);
    int rv = Reprez(v,tata);
    if(h[ru]>h[rv]) //subarborele cu radacina ru este mai inalt => atasam rv la ru
        tata[rv] = ru;
    else{
        tata[ru]=rv;
        if(h[ru]==h[rv]) //daca ambii subarbori erau de h egal => prin atasarea unuia la celalalt nivelul total al subarborelui creste cu 1
            h[rv]++;
    }
}

void kruskal(const int& n, const int& m, vector<Muchie>& lista_muchii, long long& cost, 
            vector<pair<int,int>>& muchii_apcm, vector<int>& h, vector<int>& tata){
            
        int nr_muchii_arbore=0;
        sort(lista_muchii.begin(),lista_muchii.end()); //sortam muchii crescator dupa cost

        for(int i=0; i<m; i++){
            int u = lista_muchii[i].x;
            int v = lista_muchii[i].y;
            if(Reprez(u,tata)!=Reprez(v,tata)){
                nr_muchii_arbore++;
                cost+=lista_muchii[i].cost;
                muchii_apcm.push_back({u,v});
                Reuneste(u,v,tata,h);
                if(nr_muchii_arbore==n-1)
                    return;
            }
        }
}

int main()
{
    int n,m;
    fin>>n>>m;
    vector<Muchie> lista_muchii(m);
    for(int i=0; i<m; i++)
        fin>>lista_muchii[i].x>>lista_muchii[i].y>>lista_muchii[i].cost;
    fin.close();

    long long cost=0;
    vector<pair<int,int>> muchii_apcm; //muchiil e arborelui partial de cost minim
    vector<int> h(n+1,0); //le initializam deja cu 0
    vector<int> tata(n+1,0);
    kruskal(n,m,lista_muchii,cost,muchii_apcm,h,tata);
    
    fout<<cost<<'\n'<<n-1<<'\n';
    for(const auto& muchie: muchii_apcm){
        fout<<muchie.first<<" "<<muchie.second<<'\n';
    }
    fout.close();
    return 0;
}