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



using namespace std;

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

struct muchie {
    int cost;
    int x, y;
    muchie() = default;
    muchie(int x, int y, int cost)
    {
        this->x = x;
        this->y = y;
        this->cost = cost;
    }

};

int *h, *tata;
vector<muchie> muchii;
vector<muchie> apm;
int n, m;


void Citire()
{
    fin >> n >> m;
    h = new int[n + 1];
    tata = new int[n + 1];
    

    for(int i = 1; i <= m; i ++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        muchii.push_back(muchie(x, y, c));
    }
}


int Reprez(int);
void Reuneste(int , int);

int main()
{
    Citire();

    sort(muchii.begin(), muchii.end(), 
        [](muchie a, muchie b) {return a.cost < b.cost;});
    // cout << "-------------------------------------------" << endl;
    // for(auto m : muchii)
    // {
    //     cout << "(" << m.x << ", " << m.y << ") " << m.cost << endl;
    // }
    int suma = 0;
    for(auto m : muchii)
    {
        if (Reprez(m.x) != Reprez(m.y))
        {
            suma += m.cost;
            apm.push_back(m);
            Reuneste(m.x, m.y);
        }
    }

    fout << suma << '\n';
    fout << apm.size() << '\n';
    for (auto m : apm)
    {
        fout << m.x << " " << m.y << '\n';
    }

    return 0;
}

int Reprez(int x)
{
    if (tata[x] == 0)
        return x;
    tata[x] = Reprez(tata[x]);
    return tata[x];
}

void Reuneste(int x, int y)
{
    int rx = Reprez(x), ry = Reprez(y);

    if (h[rx] > h[ry])
    {
        tata[ry] = rx;
    }
    else {
        tata[rx] = ry;
        if (h[rx] == h[ry])
            h[ry]++;
    }
}