#include <iostream>
#include <fstream>
#include <vector>
#define VMAX 200000
#define EMAX 400000

using namespace std;

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

class Edge
{
public:
    int x, y, cost;
    Edge(int x = 0, int y = 0, int cost = 0) : x(x), y(y), cost(cost) {}
    bool operator<(Edge other) const
    {
        return cost < other.cost;
    }
    bool operator>(Edge other) const
    {
        return cost > other.cost;
    }
};

int V, E, x, y, cost;
Edge edges[EMAX];
Edge result[VMAX];

int partitie(int st, int dr)
{
    int i = st - 1, j = dr + 1;
    Edge pivot = edges[st + rand() % (dr - st + 1)];
    Edge aux;

    while (1)
    {
        do
            i++;
        while (edges[i] < pivot);
        do
            j--;
        while (edges[j] > pivot);
        if (i >= j)
            return j;
        aux = edges[i], edges[i] = edges[j], edges[j] = aux;
    }
}

void quickSort(int st, int dr)
{
    int pivot;
    if (st < dr)
    {
        int pivot = partitie(st, dr);
        quickSort(st, pivot);
        quickSort(pivot + 1, dr);
    }
}

int tree_id[VMAX];

int main()
{
    fin >> V >> E;

    for (int i = 0; i < E; ++i)
    {
        fin >> x >> y >> cost;
        edges[i] = Edge(x - 1, y - 1, cost);
    }

    quickSort(0, E - 1);

    for (int i = 0; i < V; ++i)
        tree_id[i] = i;

    int total_weight = 0;
    int contor = 0;

    for (int i = 0; i < E; ++i)
        if (tree_id[edges[i].x] != tree_id[edges[i].y])
        {
            total_weight += edges[i].cost;
            result[contor++] = edges[i];
            int old_id = tree_id[edges[i].x];
            int new_id = tree_id[edges[i].y];

            for (int j = 0; j < V; ++j)
                if (tree_id[j] == old_id) tree_id[j] = new_id;
        }

    fout << total_weight << '\n' << V - 1 << '\n';

    for (int i = 0; i < V - 1; ++i)
        fout << result[i].x + 1 << " " << result[i].y + 1 << '\n';

    fin.close();
    fout.close();
    return 0;
}