/*
    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
class Edge {
    int u;
    int v;
    double w;
public:
    Edge(int u = 0, int v = 0, double w = 0){
        this->u = u;
        this->v = v;
        this->w = w;
    }
    Edge& operator=(const Edge& ob){
        if(this != &ob){
            this->u = ob.u;
            this->v = ob.v;
            this->w = ob.w;
        }
        return *this;
    }
    bool operator < (Edge ob) const{
        return this->w < ob.w;
    }
    int getU() const{
        return u;
    }
    int getV() const{
        return v;
    }
    double getW() const{
        return w;
    }

} *edges;
class MST{ // Minimum Spanning Tree = Arbore parțial de cost minim
    int numberOfEdges;
    double cost;
    Edge *edges;
public:
    MST(int E = 0){
        numberOfEdges = 0;
        cost = 0;
        edges = new Edge[E];
    }
    ~MST(){
        delete[] edges;
    }
    void addEdge(const Edge& ob){
        edges[numberOfEdges++] = ob;
        cost += ob.getW();
    }
    int getNumberfEdges() const{
        return numberOfEdges;
    }
    double getCost() const{
        return cost;
    }
    Edge* getEdges(){
        return edges;
    }
} *mst;

void Init(){
    edges = new Edge [E];
    mst   = new MST(E);
    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[i] = Edge(u, v, w);
    }
}

void Print(){
    fout << mst->getCost() << '\n';
    fout << mst->getNumberfEdges() << '\n';
    auto tempEdges = mst->getEdges();
    for(int i = 0; i < mst->getNumberfEdges(); i++){
        fout << tempEdges[i].getU() << ' ' << tempEdges[i].getV() << '\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, edges+E);
    // 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;
        u = edges[i].getU();
        v = edges[i].getV();
        if(Find(u) != Find(v)) {
            Union(u, v);
            mst->addEdge(edges[i]);
        }
    }
}

int main() {
    Read();
    sort(edges, edges+E);
    Kruskal();
    Print();
    delete[] edges;
    delete mst;
    return 0;
}