#include <iostream>
#include <fstream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;

int n;
vector <vector<int>> muchiiCuCost;
ifstream fin("apm.in");
ofstream fout("apm.out");

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

int main()
{
    int m, st, dr, cost;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> st >> dr >> cost;
        muchiiCuCost.push_back({st, dr, cost});
    }
    vector <vector <int>> rez;
    vector <int> tata(n + 1);
    for (int i = 1; i <= n; 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  nod1, nod2, tata1, tata2, nrMuchiiAPM = 0, index_muchie = 0;
    long long cost_total = 0;
    while (nrMuchiiAPM < n - 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 = nod1;
        tata2 = nod2;
        while (tata1 != tata[tata1])
            tata1 = tata[tata1];
        while (tata2 != tata[tata2])
            tata2 = tata[tata2];
        if (tata1 != tata2) ///am gasit muchie de adaugat in APM
        {
            if (tata1 < tata2)
                tata[tata1] = tata[tata2];
            else
                tata[tata2] = tata[tata1];
            rez.push_back({nod1, nod2});
            cost_total = cost_total + muchiiCuCost[index_muchie][2];
            nrMuchiiAPM++;
        }
        index_muchie++;
    }
    fout << cost_total << "\n";
    fout << nrMuchiiAPM << "\n";
    for (int i = 0; i < rez.size(); i++)
       fout << rez[i][0] << " " << rez[i][1] << "\n";
    fin.close();
    fout.close();
    return 0;
}