#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

#define edge pair<int,int>


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

class Graph {
private:
    vector<pair<int, pair<int, int>>> G; // graph
    vector<pair<int, pair<int, int>>> T; // mst
    vector<int> parent;
    int V, cost; // number of vertices/nodes in graph
public:
    Graph(int V);
    void AddWeightedEdge(int u, int v, int w);
    int find_set(int i);
    void union_set(int u, int v);
    void kruskal();
    void print();
};
Graph::Graph(int V) {
    parent = vector<int>(V);
    for (int i = 0; i < V; i++)
        parent[i] = i;
    cost = 0;
    G.clear();
    T.clear();
}
void Graph::AddWeightedEdge(int u, int v, int w) {
    G.push_back(make_pair(w, make_pair(u, v)));
}
int Graph::find_set(int i) {
    // If i is the parent of itself
    if (i == parent[i])
        return i;
    else
        // Else if i is not the parent of itself
        // Then i is not the representative of his set,
        // so we recursively call Find on its parent
        return find_set(parent[i]);
}

void Graph::union_set(int u, int v) {
    parent[u] = parent[v];
}
void Graph::kruskal() {
    int i, uRep, vRep;
    sort(G.begin(), G.end()); // increasing weight
    for (i = 0; i < G.size(); i++) {
        uRep = find_set(G[i].second.first);
        vRep = find_set(G[i].second.second);
        if (uRep != vRep) {
            T.push_back(G[i]);
            cost += G[i].first; // add to tree
            union_set(uRep, vRep);
        }
    }
}
void Graph::print() {
    fout << cost << "\n" << T.size() << "\n";
    for (int i = 0; i < T.size(); i++) {
        fout << T[i].second.second+1 << " " << T[i].second.first+1;
        fout << "\n";
    }
}
int main() {
    int n, m;

    fin >> n >> m;

    Graph g(n);

    for(int i=0; i<m; i++)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        x--; y--;
        g.AddWeightedEdge(x, y, cost);
    }
    g.kruskal();
    g.print();
    fin.close();
    fout.close();
    return 0;
}