/*
    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
struct Edge {
    int u;
    int v;
    double w;
    Edge(int u = 0, int v = 0, double w = 0):u(u), v(v), w(w){}
    bool operator < (Edge ob) const{
        return this->w < ob.w;
    }
} *edges;
double cost;
vector<pair<int, int>> mst; // Minimum Spanning Tree = Arbore parțial de cost minim

void Init(){
    edges = new Edge [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 << 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, 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].u;
        v = edges[i].v;
        if(Find(u) != Find(v)) {
            Union(u, v);
            mst.emplace_back(u, v);
            cost += edges[i].w;
        }
    }
}

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