#include <fstream>
#include <vector>
#include <algorithm>

class SetGroup
{
private:
    std::vector<int> v;
    inline int get(int x)
    {
        while(v[x] != 0) x = v[x];
        return x;
    }
    inline void mark(int x, int mark)
    {
        int aux;
        while(v[x] != 0) {
            aux = v[x];
            v[x] = mark;
            x = aux;
        }
    }
public:
    SetGroup()
    {
    }
    SetGroup(int n_sets) : v(n_sets+1)
    {
    }
    bool areJoint(int x, int y)
    {
        int a = get(x);
        int b = get(y);
        mark(x, a);
        mark(y, b);
        return a == b;
    }
    void uniteSets(int x, int y)
    {
        int a = get(x);
        int b = get(y);
        if(a != b) v[a] = b;
    }
    void addSet()
    {
        v.push_back(0);
    }
    int getSize()
    {
        return v.size();
    }
};
struct Edge
{
    int x, y, w;
    Edge(int arg_x, int arg_y, int arg_w) : x(arg_x), y(arg_y), w(arg_w)
    {
    }
    bool operator<(const Edge& edge) const
    {
        return w < edge.w;
    }
};
Edge makeEdge(int x, int y, int w)
{
    Edge edge(x, y, w);
    return edge;
}

int n, m, w;
std::vector<Edge> edges, mst;

int main()
{
    std::ifstream in("apm.in");
    std::ofstream out("apm.out");
    in>>n>>m;
    SetGroup forest(n);
    for(int x, y, w, i = 1; i <= m; ++i) {
        in>>x>>y>>w;
        edges.push_back(makeEdge(x, y, w));
    }
    std::sort(edges.begin(), edges.end());
    for(auto& edge : edges) {
        if(!forest.areJoint(edge.x, edge.y)) {
            w += edge.w;
            forest.uniteSets(edge.x, edge.y);
            mst.push_back(edge);
        }
    }
    out<<w<<'\n';
    out<<mst.size()<<'\n';
    for(auto& edge : mst) out<<edge.x<<' '<<edge.y<<'\n';
}