#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

#define maxN 200005

using namespace std;

vector <pair <int, pair <int, int> > > edges;
vector <pair <int, int> > edgesSol;
int parent[maxN];

int getRoot(int node) {
    int R;

    for(R = node; R != parent[R]; R = parent[R]);

    return R;
}

void setRoot(int x, int y) {
    parent[getRoot(x)] = getRoot(y);
}

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

    int N, M;
    f >> N >> M;

    int x, y, c, costSol = 0;
    for (int i = 0; i < M; ++i) {
        f >> x >> y >> c;

        edges.push_back(make_pair(c, make_pair(x, y)));
    }


    for (int i = 1; i <= N; ++i) {
        parent[i] = i;
    }

    sort(edges.begin(), edges.end());

    for (unsigned int i = 0; i < edges.size(); ++i) {
        int edgeX = edges[i].second.first;
        int edgeY = edges[i].second.second;
        int edgeCost = edges[i].first;

        if (getRoot(edgeX) == getRoot(edgeY)) {
            continue;
        }

        costSol += edgeCost;
        edgesSol.push_back(make_pair(edgeX, edgeY));
        setRoot(edgeX, edgeY);
    }

    g << costSol << "\n" << edgesSol.size() << "\n";
    for (unsigned int i = 0; i < edgesSol.size(); ++i) {
        g << edgesSol[i].first << " " << edgesSol[i].second << "\n";
    }

    return 0;
}