/*
 * https://www.infoarena.ro/problema/apm 100p
 * O((V+E)*logV);
 */
#include <bits/stdc++.h>

using namespace std;

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


int V, E;
vector<vector<pair<int, int>>> adjList;

void init(){
    adjList.resize(V+1);
}

void read(){
    in >> V >> E;
    init();
    for(int i = 0; i < E; i++){
        int u, v, w;
        in >> u >> v >> w;
        adjList[u].emplace_back(v, w);
        adjList[v].emplace_back(u, w);
    }
}

/*
void print(int totalWeight, const vector<Edge>& mst){
    out << totalWeight << '\n';
    out << mst.size() << '\n';
    for(const auto& edge: mst){
        out << edge.u << ' ' << edge.v << '\n';
    }
}
*/

void prim(){
    /*
     * Asociem fiecărui vârf u următoarele informaţii (etichete)
     * pentru a reține muchia de cost minim care îl unește de un vârf selectat deja în arbore:
     * -> parent: acest vârf din arbore pentru care se realizează minimul
     * -> d: costul minim al unei muchii de la u la un vârf selectat deja în arbore
     * (u, parent[u]) este muchia de cost minim de la u la un vârf din arbore
     */
    int totalWeight = 0;
    vector<bool> visited(V+1);
    vector<int> parent(V+1);
    vector<int> d(V+1, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> heap;
    d[1] = 0;
    //La un pas: se alege un vârf u cu eticheta d minimă care nu este încă în arbore şi se adaugă la arbore muchia (tata[u], u)
    heap.push({d[1], 1});
    while(!heap.empty()){
        int finalWeight = heap.top().first;
        int u = heap.top().second;
        heap.pop();
        if(visited[u])
            continue;
        visited[u] = true;
        totalWeight += finalWeight;
        for(const auto & edge: adjList[u]){
            int v = edge.first;
            int w = edge.second;
            if(visited[v])
                continue;
            if(w < d[v]){
               d[v] = w;
               parent[v] = u;
            }
            heap.push({d[v], v});
        }
    }
    out << totalWeight << '\n';
    out << V-1 << '\n';
    for(int u = 2; u <= V; u++){
        out << parent[u] <<  ' ' << u << endl;
    }
}

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