#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 parent[VMAX], rang[VMAX];

int gaseste(int i)
{
    if (i == parent[i])
        return i;
    return parent[i] = gaseste(parent[i]);
}

void uneste(int x, int y)
{
    int a = gaseste(x);
    int b = gaseste(y);

    if (rang[a] > rang[b]) swap(a, b);

    parent[a] = b;
    if (rang[a] == rang[b])
        ++rang[a];
}

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)
        parent[i] = i, rang[i] = 0;

    int total_weight = 0;
    int contor = 0;

    for (int i = 0; i < E; ++i)
    {
        int u = gaseste(edges[i].x), v = gaseste(edges[i].y);

        if (u != v)
        {
            uneste(u, v);
            total_weight += edges[i].cost;
            result[contor++] = edges[i];
        }
    }

    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;
}