/*#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 501100
using namespace std;

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

int n, m;

struct Muchie {
    int x, y, cost;
}e[NMAX], answer[NMAX];

bool cmp(Muchie e1, Muchie e2) {
    return ( (e1.cost > e2.cost)? false:true );
}

int tata[NMAX], fiu[NMAX], sizeOf[NMAX], nextElem[NMAX];

void mergeElem(int m1, int m2) {

    sizeOf[tata[m2]] += sizeOf[tata[m1]];
    int fiuMare = fiu[tata[m2]];
    int tataMic = tata[m1];
    nextElem[fiuMare] = tataMic;
    fiu[tata[m2]] = fiu[tata[m1]];
    int currentElem = tata[m1];
    int lastNode = fiu[tata[m1]];
    while (currentElem != lastNode) {
        tata[currentElem] = tata[m2];
        currentElem = nextElem[currentElem];
    }
    tata[currentElem] = tata[m2];

}


int main() {

    f >> n >> m;
    for (int i = 0; i < m; ++i) {
        f >> e[i].x >> e[i].y >> e[i].cost;
        e[i].x --;
        e[i].y --;
    }

    sort(e, e + m, cmp);

    for (int i = 0; i < n; ++i) {
        tata[i] = i;
        fiu[i] = i;
        sizeOf[i] = 1;
        nextElem[i] = i;
    }
    long long int cost = 0;
    int nrElem = 0;
    for (int i = 0; nrElem < n - 1; ++i) {
        if (tata[e[i].x] != tata[e[i].y]) {

            answer[nrElem].x = e[i].x;
            answer[nrElem].y = e[i].y;

            nrElem ++;
            cost = cost + e[i].cost;

            if (sizeOf[tata[e[i].x]] > sizeOf[tata[e[i].y]] ) {
                mergeElem(e[i].y, e[i].x);
            } else {
                mergeElem(e[i].x, e[i].y);
            }
        }
    }

    g << cost << "\n" << nrElem << "\n";

    for (int i = 0; i < nrElem; ++i) {
        g << answer[i].x + 1 << " " << answer[i].y + 1 << "\n";
    }

    return 0;
}*/#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 500100
using namespace std;

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

int n, m;

pair< int, pair<int, int> > edgeArray[NMAX];

int father[NMAX], child[NMAX], dim[NMAX], nextNode[NMAX];

bool samePartition(int x, int y) {
    return (father[x] == father[y]);
}

void merge(int x, int y) {
    dim[father[y]] += dim[father[x]];
    nextNode[child[father[y]]] = father[x];
    child[father[y]] = child[father[x]];
    int currentNode = father[x];
    int lastNode = child[father[x]];
    while(currentNode != lastNode) {
        father[currentNode] = father[y];
        currentNode = nextNode[currentNode];
    }
    father[currentNode] = father[y];
}

pair<int, int> answer[NMAX];

int main() {

    f >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, cost;
        f >> x >> y >> cost;
        x --;
        y --;
        pair<int, int> p1(x, y);
        edgeArray[i].first = cost;
        edgeArray[i].second = p1;
    }

    for (int i = 0; i < n; ++i) {
        father[i] = i;
        dim[i] = 1;
        nextNode[i] = i;
        child[i] = i;
    }
    sort(edgeArray, edgeArray + m);
    int cost = 0;
    int nrElem = 0;
    for (int i = 0; nrElem < n - 1; ++i) {
        int node1 = edgeArray[i].second.first;
        int node2 = edgeArray[i].second.second;
        if (!samePartition(node1, node2)) {
            cost += edgeArray[i].first;
            answer[nrElem] = edgeArray[i].second;
            nrElem ++;
            if (dim[father[node1]] < dim[father[node2]]) {
                merge(node1, node2);
            } else {
                merge(node2, node1);
            }
        }
    }

    g << cost << "\n";
    g << nrElem << "\n";
    for (int i = 0; i < nrElem; ++i) {
        g << answer[i].first + 1 << " " << answer[i].second + 1 << "\n";
    }

    return 0;
}