#include <fstream>
#include <vector>
#include <utility>
#include <cstdlib>
#include <ctime>

struct Edge
{
    int x, y;
    int weight;
    Edge() : x(), y(), weight() {}
    Edge(int a, int b, int c) : x(a), y(b), weight(c) {}
};

struct Node
{
    int parent, ranks;
    Node() : parent(), ranks() {}
    Node(int a) : parent(a), ranks(0) {}
};

void quicksort(Edge *A, int left, int right);

int finds(Node *A, int i);
bool unions(Node *A, int i, int j);

int main()
{
    srand(time(NULL));

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

    int nV, nE, a, b, c;
    long long sum(0);

    in >> nV >> nE;

    Edge *Arr = new Edge[nE];

    Node *Brr = new Node[nV + 1];

    std::vector<Edge> myV;

    bool ok;

    for(int i = 1; i <= nV; i++)
        Brr[i] = Node(i);

    for(int i = 0; i < nE; i++)
    {
        in >> a >> b >> c;
        Arr[i] = Edge(a, b, c);
    }

    quicksort(Arr, 0, nE - 1);

    for(int i = 0; i < nE; i++)
    {
        Edge e = Arr[i];
        ok = unions(Brr, e.x, e.y);
        if(ok)
        {
            sum += e.weight;
            myV.push_back(e);
        }
    }

    out << sum << '\n' << myV.size() << '\n';

    for(unsigned i = 0; i < myV.size(); i++)
        out << myV[i].x << ' ' << myV[i].y << '\n';

    return 0;
}

void quicksort(Edge *A, int left, int right)
{
    if(left >= right) return;
    int l = left, r = right, pivot = A[left + rand() % (right - left)].weight;
    while(l < r)
    {
        while(A[l].weight < pivot) l++;
        while(A[r].weight > pivot) r--;
        if(l <= r)
        {
            std::swap(A[l], A[r]);
            l++;
            r--;
        }
    }
    quicksort(A, left, r);
    quicksort(A, l, right);
}

int finds(Node *A, int i)
{
    if(i != A[i].parent)
        A[i].parent = finds(A, A[i].parent);
    return A[i].parent;
}

bool unions(Node *A, int i, int j)
{
    int a = finds(A, i), b = finds(A, j);
    if(a == b) return false;
    if(A[a].ranks == A[b].ranks)
    {
        A[a].ranks++;
        A[b].parent = a;
    }
    else if(A[a].ranks < A[b].ranks)
        A[a].parent = b;
    else A[b].parent = a;
    return true;
}