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

using namespace std;

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

#define pb push_back

int n, m, usedEdges, sum;

struct edge
{
    int x, y, cost;
    bool used;
};

vector <edge> edges;
vector <int> parent, height;

int findParent(int node)
{
    if(node == parent[node])
        return parent[node];
    return parent[node] = findParent(parent[node]);
}

void setsUnion(int i)
{
    int parentA, parentB;
    parentA = findParent(edges[i].x);
    parentB = findParent(edges[i].y);

    if(parentA != parentB)
    {
        edges[i].used = 1;
        usedEdges ++;
        sum += edges[i].cost;
        if(height[parentA] < height[parentB])
            swap(parentA, parentB);
        parent[parentB] = parentA;
        if(height[parentA] == height[parentB])
        {
            parent[parentB] = parentA;
            height[parentA] ++;
        }
    }
}

int main()
{
    in >> n >> m;
    parent.resize(n + 1);
    height.resize(n + 1, 1);
    for(int i = 1; i <= n ; i++)
        parent[i] = i;

    for(int i = 0; i < m; i ++)
    {
        int a, b, c;
        in >> a >> b >> c;
        edges.pb({a, b, c, 0});
    }

    sort(edges.begin(), edges.end(), [](const edge &a, const edge &b)
    {
        return a.cost < b.cost;
    });

//    for(edge i : edges)
//    {
//        out << i.x << " " << i.y << " " << i.cost << "\n";
//    }
    for(int i = 0; i < m  &&  usedEdges < n - 1; i++)
    {
        setsUnion(i);
//        out << edges[i].x << " " << edges[i].y << " " << edges[i].cost << "\n";
//        for(int j = 1; j <= n; j++)
//            out << parent[j] << " ";
//        out << "\n";
//        for(int j = 1; j <= n; j++)
//            out << height[j] << " ";
//        out << "\n";
//        out << "\n";
//        out << i << "\n";
    }

    out << sum << "\n";
    out << usedEdges << "\n";
    for(int i = 0; i < m; i ++)
    {
        if(edges[i].used == 1)
            out << edges[i].x << " " << edges[i].y << "\n";
    }
    return 0;
}