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

struct Edge
{
    int x, y, c;
};

bool cmp(Edge edge1, Edge edge2);
int getRoot(int x, int disj[]);
void unite(int x, int y, int disj[]);

int main()
{
    int N, M, i;
    ifstream f("apm.in");
    f >> N >> M;
    Edge e[M + 1];
    int disj[N + 1];
    for (i = 1; i <= M; i++)
        f >> e[i].x >> e[i].y >> e[i].c;
    f.close();

    for (i = 1; i <= N; i++)
        disj[i] = i;
    sort(e + 1, e + M + 1, cmp);

    int k = 0, totalCost = 0;
    vector<Edge> result;
    for (i = 1; i <= M; i++)
        if (getRoot(e[i].x, disj) != getRoot(e[i].y, disj))
        {
            k++;
            totalCost += e[i].c;
            result.push_back(e[i]);
            unite(getRoot(e[i].x, disj), getRoot(e[i].y, disj), disj);
        }

    ofstream g("apm.out");
    g << totalCost << '\n' << k << '\n';

    for (i = 0; i < result.size(); i++)
        g << result[i].x << " " << result[i].y << '\n';
    g.close();
    return 0;
}

bool cmp(Edge edge1, Edge edge2)
{
    if (edge1.c < edge2.c)
        return true;

    return false;
}

int getRoot(int x, int disj[])
{
    int root = x;
    while (root != disj[root])
        root = disj[root];

    int aux = x;
    while (x != disj[x])
    {
        aux = disj[x];
        disj[x] = root;
        x = aux;
    }

    return root;
}

void unite(int x, int y, int disj[])
{
    disj[y] = x;
}