/*
 * O(E*logE);
 */
#include <bits/stdc++.h>

using namespace std;

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

struct Edge{
    int u, v, w;
    bool operator < (const Edge& ob) const{
        return this->w < ob.w;
    }
};

int V, E;
vector<Edge> edges;
vector<int> parent, h;

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

void read(){
    in >> V >> E;
    init();
    for(int i = 0; i < E; i++){
        int u, v, w;
        in >> u >> v >> w;
        edges.push_back({u, v, 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';
    }
}

int Find(int u){
    while(parent[u] != 0)
        u = parent[u];
    return u;
}
void Union(int u, int v){
    int root_u = Find(u);
    int roo_v  = Find(v);
    if(h[root_u] > h[roo_v])
        parent[roo_v] = root_u;
    else{
        parent[root_u] = roo_v;
        if(h[root_u] == h[roo_v])
            h[roo_v]++;
    }
}

void kruskal(){
    int totalWeight = 0;
    vector<Edge> mst; // minimum spanning tree
    sort(edges.begin(), edges.end());
    for(int i = 1; i <= V; i++){
        parent[i] = h[i] = 0;
    }
    int numberOfEdges = 0;
    for(const auto& edge: edges){
        int u = edge.u;
        int v = edge.v;
        if(Find(u) != Find(v)){
            mst.push_back(edge);
            Union(u, v);
            totalWeight += edge.w;
            numberOfEdges++;
            if(numberOfEdges == V-1)
                return print(totalWeight, mst);
        }
    }
}

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