/*
    Kruskal Algorithm
    https://www.infoarena.ro/problema/apm
    Complexity: O(m*log n)
    100p
*/
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

int V, E; // numarul de noduri & muchii
vector<int> parrent; // vector de tati
vector<int> h;       // vector de inaltimi pentru subarbori
vector<pair<double, pair<int, int>>> edges;
double cost;
vector<pair<int, int>> mst; // minimum spanning tree = arbore parțial de cost minim

void Init(){
    h.resize(V+1, 0);
    // initial, parintele fiecărui nod este 0
    parrent.resize(V+1, 0);
}

void Read(){
    fin >> V >> E;
    Init();
    for(int i = 0; i < E; i++){
        int u, v;
        double w;
        fin >> u >> v >> w;
        edges.push_back({w, {u, v}});
    }
}

void Print(){
    fout << cost << '\n';
    fout << mst.size() << '\n';
    for(const auto & e: mst){
        fout << e.first << ' ' << e.second << '\n';
    }
}

int Find(int u){
    while(parrent[u])
        u = parrent[u];
    return u;
}

void Union(int u, int v){
    int ru, rv;
    ru = Find(u);
    rv = Find(v);
    if(h[ru] > h[rv])
        parrent[rv] = ru;
    else {
        parrent[ru] = rv;
        if(h[ru] == h[rv])
            h[rv]++;
    }
}

void Kruskal(){
    // se ordonează muchiile grafului crescător dupa cost
    sort(edges.begin(), edges.end());
    // pentru fiecare muchie analizată
    for(int i = 0; i < E; i++){
        // daca extremitățile muchiei fac parte din subarbori diferiți, aceștia se vor reuni,
        // iar muchia respectivă va face parte din APM
        int u, v;
        double w;
        w = edges[i].first;
        u = edges[i].second.first;
        v = edges[i].second.second;
        if(Find(u) != Find(v)) {
            Union(u, v);
            mst.emplace_back(u, v);
            cost += w;
        }
    }
}

int main() {
    Read();
    Kruskal();
    Print();
    return 0;
}