#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct Muchie
{
    int u, v, cost;
};

vector<Muchie> muchii;

bool comparaMuchii(Muchie a, Muchie b)
{
    return a.cost < b.cost;
}

void kruskal(int n)
{
    sort(muchii.begin(), muchii.end(), comparaMuchii);

    vector<int> r(n);
    for(int i = 0; i < n; i++)
        r[i] = i + 1;
    
    vector<Muchie> apcm;
    int costTotal = 0;
    int muchiiSelectate = 0;
    for(Muchie muchie : muchii)
    {
        int u = muchie.u;
        int v = muchie.v;
        if(r[u - 1] != r[v - 1])
        {
            apcm.push_back(muchie);
            costTotal += muchie.cost;
            muchiiSelectate++;

            int reprezentantVechi = r[v - 1];
            int reprezentantNou = r[u - 1];
            for(int k = 0; k < n; k++)
                if(r[k] == reprezentantVechi)
                    r[k] = reprezentantNou;
            if(muchiiSelectate == n - 1)
                break;
        }
    }
    g << costTotal << "\n";
    g << apcm.size() << "\n";
    for(Muchie muchie : apcm)
        g << muchie.u << " " << muchie.v << "\n";
}

int main()
{
    int n, m;
    f >> n >> m;
    muchii.resize(m);
    for(int i = 0; i < m; i++)
        f >> muchii[i].u >> muchii[i].v >> muchii[i].cost;
    kruskal(n);
    return 0;
}