// Lab3.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

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

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int parinte[200001], height[200001];

struct muchie {
    int x, y, c;
};

struct lista {
    int x, y;
};

int Find(int x) {
    while (x != parinte[x]) {
        x = parinte[x];
    }
    return x;
}

//void Union(int x, int y) { // x si y noduri
//    x = Find(x); // gaseste parintele subarborelui din care face parte x--> creste in arbore pana la radacina
//    y = Find(y); 
//    if (x != y) {
//        if (height[x] < height[y]) {
//            parinte[x] = y; // y devine parintele lui x (x fiind parte din subarborele cel mai mic) pentru a reunii arborele
//        }
//        else {
//            if (height[y] < height[x]) {
//                parinte[y] = x;
//            }
//            else {
//                parinte[x] = y;
//                height[y]++;
//            }
//        }
//    }
//
//}

int main()
{
    int n, m, costTotal = 0, nr = 0;
    vector<muchie> v;
    vector<int> M[200001];

    fin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int xC, yC, cC; // x curent y curent c curent
		fin >> xC >> yC >> cC;
        muchie curenta;
        curenta.x = xC;
        curenta.y = yC;
        curenta.c = cC;
        v.push_back(curenta);
    }

    sort(v.begin(), v.end(), [](muchie a, muchie b) {
        return a.c < b.c;
    });

    // initial toate nodurile sunt de sine statatoare --> reprezentatii sunt ei insasi si inaltimile sunt 1
    for (int i = 1; i <= n; i++) {
        parinte[i] = i;
        height[i] = 1;
    }
    

    for (int i = 0; i < m; i++) {
        int nod1, nod2, costn, r1, r2;
        nod1 = v[i].x;
        nod2 = v[i].y;
        costn = v[i].c;
        r1 = Find(nod1);
        r2 = Find(nod2);
        if (r1 != r2) {
            if (height[r1] > height[r2]) {
                parinte[r2] = r1; // y devine parintele lui x (x fiind parte din subarborele cel mai mic) pentru a reunii arborele
            }
            else {
                if (height[r1] < height[r2]) {
                    parinte[r1] = r2;
                }
                else {
                    parinte[r1] = r2;
                    height[r2]++;
                }
            }
            ++nr;
            M[nr].push_back(nod1);
            M[nr].push_back(nod2);
            costTotal += costn;
        }
    }


    fout << costTotal << endl << nr << endl;
    for (int i = 1; i <= nr; i++) {
        fout << M[i][1] << " " << M[i][0] << endl;
    }
   

    return 0;
}