#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int Nmax = 200005;
const int Mmax = 400005;

struct muchie{
    int destinatie, cost;
};

struct nod{
    vector<muchie> muchii;
    bool vizitat;
};

int n, m, suma_apm;
nod noduri[Nmax];
vector<pair<int, int>> muchii_apm;
priority_queue<pair<int, pair<int, int>>> q;

void citire(){
    int nod1, nod2, cost;

    fin >> n >> m;

    for(int i = 1; i <= m; i++){
        fin >> nod1 >> nod2 >> cost;

        noduri[nod1].muchii.push_back({nod2, cost});
        noduri[nod2].muchii.push_back({nod1, cost});
    }
}

void preinitializare(){
    for(int i = 1; i <= n; i++){
        noduri[i].vizitat = 0;
    }
}

void procesare_nod_inceput(int nod){
    for(muchie edge : noduri[nod].muchii){
        q.push({-edge.cost, {nod, edge.destinatie}});
    }
    noduri[nod].vizitat = 1;
}

void prim(){
    int nod, cost;
    pair<int, int> pereche_noduri;

    procesare_nod_inceput(1);

    suma_apm = 0;
    while(!q.empty()){
        cost = -q.top().first;
        pereche_noduri = q.top().second;
        nod = q.top().second.second;
        q.pop();

        if(!noduri[nod].vizitat){
            suma_apm += cost;
            muchii_apm.push_back(pereche_noduri);
            noduri[nod].vizitat = 1;

            for(muchie edge : noduri[nod].muchii){
                q.push({-edge.cost, {nod, edge.destinatie}});
            }
        }
    }
}

void afisare(){
    fout << suma_apm << '\n';
    fout << muchii_apm.size() << '\n';
    for(pair<int, int> edge : muchii_apm){
        fout << edge.first << ' ' << edge.second << '\n';
    }
}

int main(){
    citire();

    preinitializare();
    prim();

    afisare();

    return 0;
}