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

///---------------------Graf Ponderat - Muchii cu costuri-------------------------------
bool comparaCost (vector <int> v1, vector <int> v2)
{
    return v1[2] < v2[2];
}

class GrafPonderat
{
    private:
        int nrN, nrM;
        vector <vector <int>> muchiiCuCost;
        int find_tata(int, vector <int>);
        void set_tata(int, int, vector <int> &);
    public:
        GrafPonderat(int, int, vector <vector <int>>);
        void apmKruskal(ostream &);
};

GrafPonderat :: GrafPonderat(int nrNoduri, int nrMuchii, vector <vector <int>> muchiiCost)
{
    nrN = nrNoduri;
    nrM = nrMuchii;
    muchiiCuCost = muchiiCost;
}

int GrafPonderat :: find_tata(int nod, vector <int> tata)
{
    if (nod == tata[nod])
        return nod;
    int res = find_tata(tata[nod], tata);
    return res;
}

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

void GrafPonderat :: apmKruskal(ostream &out)
{
    vector <pair<int, int>> rez;
    vector <int> tata(nrN + 1);
    for (int i = 1; i <= nrN; i++)
        tata[i] = i;
    sort (muchiiCuCost.begin(), muchiiCuCost.end(), comparaCost); ///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(make_pair(nod1, nod2));
            nrMuchiiAPM++;
        }
        index_muchie++;
    }
    out << cost_total << "\n";
    out << nrMuchiiAPM << "\n";
    for (int i = 0; i < rez.size(); i++)
       out << rez[i].first << " " << rez[i].second << "\n";
}

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n, m, st, dr, cost;
    //cout << "Introduceti numarul de noduri: ";
    //cin >> n;
    //cout << "Introduceti numarul de muchii: ";
    //cin >> m;
    //cout << "Introduceti muchiile si costul acestora: " << "\n";
    fin >> n >> m;
    vector <vector <int>> muchiiCost;
    for (int i = 1; i <= m; i++)
    {
       // cin >> st >> dr >> cost;
        fin >> st >> dr >> cost;
        muchiiCost.push_back({st, dr, cost});
    }
    GrafPonderat g(n, m, muchiiCost);
    g.apmKruskal(fout);
    fin.close();
    fout.close();
    return 0;
}