#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int MMAX = 4e5 + 5, NMAX = 2e5 + 5;

struct edge{

    int cost, firstNode, secondNode;
};

edge edges[MMAX];
pair<int, int> mstEdges[NMAX];

int Father[NMAX], Rank[NMAX];
int nodesCnt, edgesCnt, mstCost, mstEdgesLen;

inline bool cmp(const edge &firstEdge, const edge &secondEdge){

    return firstEdge.cost < secondEdge.cost;
}

inline void readData(){

    fin >> nodesCnt >> edgesCnt;

    int from, to, cost, idx;
    for(idx = 1; idx <= edgesCnt; ++idx){

        fin >> from >> to >> cost;
        edges[idx] = {cost, from, to};

        Father[from] = from; Father[to] = to; ///Union-Find stuff
        Rank[from] = 1; Rank[to] = 1;
    }
    sort(edges + 1, edges + 1 + edgesCnt, cmp);
}

inline int findRoot(int node){

    int root;
    for(root = node; root != Father[root]; root = Father[root]);

    int auxNode;
    while(node != Father[node]){

        auxNode = node;
        node = Father[node];
        Father[auxNode] = root;
    }

    return root;
}

inline void unite(int firstNode, int secondNode){

    if(Rank[firstNode] > Rank[secondNode])
        Father[secondNode] = firstNode;
    else
        Father[firstNode] = secondNode;

    if(Rank[firstNode] == Rank[secondNode])
        ++Rank[secondNode];
}

inline void getMST(){

    int idx, cost, firstNode, secondNode, firstRoot, secondRoot;
    for(idx = 1; idx <= edgesCnt; ++idx){

        cost = edges[idx].cost;
        firstNode = edges[idx].firstNode;
        secondNode = edges[idx].secondNode;

        firstRoot = findRoot(firstNode);
        secondRoot = findRoot(secondNode);
        if(firstRoot != secondRoot){

            unite(firstRoot, secondRoot);
            mstCost += cost;
            mstEdges[++mstEdgesLen] = {firstNode, secondNode};
        }
    }
}

inline void print(){

    fout << mstCost << '\n' << nodesCnt - 1 << '\n';

    int idx;
    for(idx = 1; idx <= mstEdgesLen; ++idx)
        fout << mstEdges[idx].first << ' ' << mstEdges[idx].second << '\n';
}

int main(){

    readData();
    getMST();
    print();
}