// https://www.infoarena.ro/problema/apm
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int N, M; // nr. noduri, nr. muchii
vector<pair<int, double>> *listaAd;
vector<int> tata;
vector<double> d;
vector<int> viz;
const int inf = 1e9;
double costTotal;

void init(){
    listaAd = new vector<pair<int, double>> [N+1]; // nod, cost
    tata    = vector<int>  (N+1);    // tata[u] = acest vârf din arbore pentru care se realizeaza minimul
    d       = vector<double>  (N+1); // d[u] = costul minim al unei muchii de la un varf selectat deja in arbore
    viz     = vector<int> (N+1);
    for(int u = 1; u <= N; u++)
        viz[u] = 0, d[u] = inf;
}

void read(){
    fin >> N >> M;
    init();
    for(int i = 0; i < M; i++){
        int u, v, c;
        fin >> u >> v >> c;
        listaAd[u].emplace_back(v, c);
        listaAd[v].emplace_back(u, c);
    }
}

void prim(int s = 1){
    priority_queue<pair<double, int>> q; // tata, d
    d[s] = 0;
    q.push({0, s});
    while(!q.empty()){
        int u = q.top().second; // varful nevizitat cu d minim
        q.pop();
        viz[u]++;
        if(viz[u] == 1){ // daca este prima extragere din q a lui u relaxam arcele
            for(const auto & p: listaAd[u]){
                auto v = p.first;
                auto c = p.second;
                if(viz[v] == 0){
                    if(c < d[v]){
                        tata[v] = u;
                        d[v] = c;
                        q.push({-d[v], v}); // distanta este pusa cu - pentru a se comporta ca min-heap
                    }
                }
            }
        }
    }
    vector<pair<int, int>> apm;
    for(int i = 2; i <= N; i++){
        costTotal += d[i];
        apm.emplace_back(i, tata[i]);
    }
    fout << costTotal << '\n';
    fout << apm.size() << '\n';
    for(const auto & muchie: apm)
        fout << muchie.first << ' ' << muchie.second << '\n';
 }

int main() {
    read();
    prim(1);
    return 0;
}