#include <bits/stdc++.h>
using namespace std;


inline bool isdigit(char ch) {
        return '0' <= ch && ch <= '9';
}

#define buffsze 8192
class inParser {
private:
        FILE *fin; char *buff; unsigned short id;
        inline char readCh( ) {
                ++id;
                if (id == buffsze) { id = 0; fread(buff, sizeof(char), buffsze, fin); }
                return buff[id];
        }
public:
        inParser (const char *name) {
                fin = fopen(name, "r");
                buff = new char[buffsze]( );
                id = buffsze - 1;
        }

        inParser& operator >> (int& num) {
                char ch;
                while (!isdigit(ch = readCh( )));
                num = ch - '0';
                while (isdigit(ch = readCh( )))
                        num = num * 10 + ch - '0';
                return *this;
        }

        inParser& operator >> (long long& num) {
                char ch;
                while (!isdigit(ch = readCh( )));
                num = ch - '0';
                while (isdigit(ch = readCh( )))
                        num = num * 10 + ch - '0';
                return *this;
        }
};

class outParser {
private:
        FILE *fout; char *buff; unsigned short id;
        inline void writeCh(char ch) {
                ++id;
                if (id == buffsze) { id = 0; fwrite(buff, sizeof(char), buffsze, fout); }
                buff[id] = ch;
        }
public:
        outParser (const char *name) {
                fout = fopen(name, "w");
                buff = new char[buffsze]( );
                id = -1;
        }

        ~outParser ( ) {
                fwrite(buff, sizeof(char), id, fout);
        }

        outParser& operator << (int num) {
                if (num < 10) writeCh(num + '0');
                else {
                        (*this) << (num / 10);
                        writeCh(num % 10 + '0');
                }
                return *this;
        }


        outParser& operator << (char ch) {
                writeCh( ch );
                return *this;
        }
};

const string filename = "apm";
inParser in ((filename + ".in").c_str( ));
outParser out ((filename + ".out").c_str( ));

const int maxcSize = 100002;

int parent[maxcSize], cSize[maxcSize];
inline int findParent(int node) {
    while (node != parent[node]) node = parent[node];
    return node;
}

inline bool connect(int nodeA, int nodeB) {
    nodeA = findParent( nodeA );
    nodeB = findParent( nodeB );

    if (nodeA == nodeB) return false;

    if (cSize[nodeA] < cSize[nodeB]) swap(nodeA, nodeB);
    cSize[nodeA] += cSize[nodeB]; parent[nodeB] = nodeA;
    return true;
}

struct type {int nodeA, nodeB, cost;};

bool cmpFunction(type a, type b) {
    return a.cost < b.cost;
}

type edges[4 * maxcSize];
pair <int , int> toShow[maxcSize];
int numNodes, numEdges, i, ans, lenShow;
int main( ) {
    in >> numNodes >> numEdges;

    for (i = 0; i < numEdges; ++i) {
        in >> edges[i].nodeA >> edges[i].nodeB >> edges[i].cost;
    }
    sort(edges, edges + numEdges, cmpFunction);

    for (i = 1; i <= numNodes; ++i) {
        parent[i] = i; cSize[i] = 1;
    }

    for (i = 0; i < numEdges; ++i) {
        if (lenShow == numNodes - 1) break;
        if (connect(edges[i].nodeA, edges[i].nodeB)) {
            toShow[++lenShow] = {edges[i].nodeA, edges[i].nodeB};
            ans += edges[i].cost;
        }
    }

    out << ans << '\n';
    out << numNodes - 1 << '\n';
    for (i = 1; i <= lenShow; ++i) out << toShow[i].first << ' ' << toShow[i].second << '\n';
    return 0;
}