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

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

struct vecin {
    int a, b, c;
};

struct nod {
    bool vizitat;
    vector<vecin> vecini;
};

bool operator < (const vecin &x, const vecin &y) {
    return x.c > y.c;
}

int n, m, i, x, y, z, cost;
priority_queue<vecin> coada;
vector<vecin> sol;
nod graf[200001];

void prim(vecin k) {
    int j;
    for(j = 0; j < graf[k.b].vecini.size(); j++) {
        if(!graf[graf[k.b].vecini[j].b].vizitat) {
            coada.push(vecin{graf[k.b].vecini[j].a, graf[k.b].vecini[j].b, graf[k.b].vecini[j].c});
        }
    }
    graf[k.b].vizitat = true;
}

int main() {
    fin >> n >> m;
    vecin aux;
    for(i = 0; i < m; i++) {
        fin >> x >> y >> z;
        aux.a = x;
        aux.b = y;
        aux.c = z;
        graf[x].vecini.push_back(aux);
        aux.a = y;
        aux.b = x;
        graf[y].vecini.push_back(aux);
    }
    aux.a = 0;
    aux.b = 1;
    aux.c = 0;
    coada.push(aux);
    while(!coada.empty()) {
        aux = coada.top();
        coada.pop();
        if(!graf[aux.b].vizitat) {
            cost += aux.c;
            sol.push_back(aux);
            prim(aux);
        }
    }
    fout << cost << '\n' << sol.size() - 1 << '\n';
    for(i = 1; i < sol.size(); i++) {
        fout << sol[i].a << ' ' << sol[i].b << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}