#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
int parent[200001], sz[200001];
int numComponents;

int findGroup(int x) {
    int root = x;
    while(parent[root] != root) {
        root = parent[root];
    }
    // path compression
    while(x != root) {
        int next = parent[x];
        parent[x] = root;
        x = next;
    }

    return root;
}

void unify(int x, int y) {
    int grX = findGroup(x);
    int grY = findGroup(y);

    if(grX != grY) {
        if(sz[grX] >= sz[grY]) {
            parent[grY] = grX;
            sz[grX] += sz[grY];
        } else {
            parent[grX] = grY;
            sz[grY] += sz[grY];
        }
        numComponents--;
    }
}

//(nod1, nod2)
vector <pair <int, int> > apmEdges;

//(cost, (nod1, nod2))
vector <pair <int, pair <int, int> > > edges;

void kruskal(int &cost, int &numEdges, vector <pair <int, int> > &apmEdges) {
    sort(edges.begin(), edges.end());
    cost = 0;
    numEdges = 0;
    for(unsigned int i = 0; i < edges.size(); ++i) {
        int edgeCost = edges[i].first;
        int nod1 = edges[i].second.first;
        int nod2 = edges[i].second.second;
        if(findGroup(nod1) != findGroup(nod2)) {
            unify(nod1, nod2);
            apmEdges.push_back(make_pair(nod1, nod2));
            numEdges++;
            cost += edgeCost;
        }
    }
}


int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n, m;
    f >> n >> m;
    for(int i = 1; i <= n; ++i) {
        parent[i] = i;
        sz[i] = 1;
    }
    for(int i = 1; i <= m; ++i) {
        int cost, nod1, nod2;
        f >> nod1 >> nod2 >> cost;
        edges.push_back(make_pair(cost, make_pair(nod1, nod2)));
    }
    int cost = 0, numEdges = 0;
    kruskal(cost, numEdges, apmEdges);
    g << cost << "\n";
    g << numEdges << "\n";
    for(int i = 0; i < numEdges; ++i) {
        g << apmEdges[i].first << " " << apmEdges[i].second << "\n";
    }
    f.close();
    g.close();
    return 0;
}