///SORA ANDREEA-IOANA, GRUPA 234
#include <iostream>
#include <fstream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

///---------------------Graf Ponderat - Muchii cu costuri-------------------------------
int find_tata(int nod, vector <int> tata)
{
    if (nod == tata[nod])
        return nod;
    int res = find_tata(tata[nod], tata);
    return res;
}

void set_tata(int nod1, int nod2, vector <int> &tata)
{
    tata[nod1] = tata[nod2];
}

void apmKruskal(ostream &out, vector <vector<int>> muchiiCuCost, int nrN)
{
    vector <vector <int>> rez;
    vector <int> tata(nrN + 1);
    for (int i = 1; i <= nrN; i++)
        tata[i] = i;
    sort (muchiiCuCost.begin(), muchiiCuCost.end(), [] (vector <int> v1, vector <int> v2){return v1[2] < v2[2];}); ///sortam muchiile crescator dupa cost
    int cost_total = 0, nod1, nod2, tata1, tata2, nrMuchiiAPM = 0, index_muchie = 0;
    while (nrMuchiiAPM < nrN - 1) ///parcurgem muchiile pana cand avem suficiente ca graful sa fie conex = (numar noduri - 1) muchii
    {
        nod1 = muchiiCuCost[index_muchie][0]; ///nod1 din muchia curenta
        nod2 = muchiiCuCost[index_muchie][1]; ///nod2 din muchia curenta
        ///cautam radacina arborilor partiali din care fac parte nodurile
        tata1 = find_tata(nod1, tata);
        tata2 = find_tata(nod2, tata);
        if (tata1 != tata2) ///am gasit muchie de adaugat in APM
        {
            cost_total = cost_total + muchiiCuCost[index_muchie][2];
            if (tata1 < tata2)
                tata[tata1] = tata[tata2];
            else
                tata[tata2] = tata[tata1];
            rez.push_back({nod1, nod2});
            nrMuchiiAPM++;
        }
        index_muchie++;
    }
    out << cost_total << "\n";
    out << nrMuchiiAPM << "\n";
    for (int i = 0; i < rez.size(); i++)
       out << rez[i][0] << " " << rez[i][1] << "\n";
}

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n, m, st, dr, cost;
    fin >> n >> m;
    vector <vector <int>> muchiiCost;
    for (int i = 1; i <= m; i++)
    {
        fin >> st >> dr >> cost;
        muchiiCost.push_back({st, dr, cost});
    }
    apmKruskal(fout, muchiiCost, n);
    fin.close();
    fout.close();
    return 0;
}