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

using namespace std;

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

vector <int> parent;
vector <int> rang; //ne intereseza doar rangul radacinilor
vector <pair  <pair <int, int>, int>  > muchiiCost; //pereche de forma ((varf1, varf2), cost)
vector <pair <int, int> > APMedges; //va contine muchiile din APM
int n, m, x, y, c, costTot = 0, cost, i;

int findRoot (int x) {
    int i, y;
    //gasim radacina lui x
    for (i = x; parent[i] != i; i = parent[i]) {}

    //comprimare
    while (parent[x] != x) {
        y = parent[x];
        parent[x] = i;
        x = y;
        rang[i]--;
    }
    return i;
}

void link (int x, int y) { //
    if (rang[x] < rang[y]) parent[x] = y;
     else {
        if (rang[x] > rang[y]) parent[y] = x;
         else {
            parent[x] = y;
            rang[y]++;
         }
     }
}

void unionSets (int x, int y) {
    link(findRoot(x), findRoot(y));
}

bool comp (const pair  <pair <int, int>, int>  & M1, const pair  <pair <int, int>, int>  & M2) {
    if (M1.second < M2.second) return true;
    return false;
}

vector <pair <int, int> > APM (vector <pair  <pair<int, int>, int>  > muchiiCost, int n, int &costTot) {
    sort (muchiiCost.begin(), muchiiCost.end(), comp); //ordonam crescator in functie de costuri
    /*for (i = 0; i < muchiiCost.size(); i++)
        cout << muchiiCost[i].first.first << " " << muchiiCost[i].first.second << " " << muchiiCost[i].second << endl;*/

    vector <pair <int, int> > APMedges;
    int x, y, cost, i;

    rang.resize(n + 1, 0);
    parent.resize(n + 1);
    for (i = 0; i < n + 1; i++) parent[i] = i;

    for (i = 0; i < muchiiCost.size(); i++) {
        x = muchiiCost[i].first.first;
        y = muchiiCost[i].first.second;
        cost = muchiiCost[i].second;

        if (findRoot(x) != findRoot(y)) {
            APMedges.push_back(make_pair(x, y));
            unionSets(x, y);
            costTot = costTot + cost;
        }
    }

    return APMedges;
}

int main()
{
    f >> n >> m;
    for (i = 0; i < m; i++) {
        f >> x >> y >> c;
        muchiiCost.push_back (make_pair(make_pair(x, y), c));
    }

    APMedges = APM(muchiiCost, n, costTot);
    g << costTot << endl;
    g << APMedges.size() << endl;

    for (i = 0; i < APMedges.size(); i++)
            g << APMedges[i].first << " " << APMedges[i].second << endl;
    //for (i = 0; i < n + 1; i++) cout << rang[i] << " ";

    f.close();
    g.close();

    return 0;
}