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

using namespace std;

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

vector<int> tata(200005);
vector<int> nr(200005);
vector<pair<int, int>> arbore;
struct muchie
{
    int stanga, dreapta, cost;
};

bool cmp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

int Find(int nod)
{
    while (nod != tata[nod])
        nod = tata[nod];
    return nod;
}

void Union(int a, int b)
{
    int radacina_a = Find(a);
    int radacina_b = Find(b);
    if (nr[radacina_a] > nr[radacina_b])
    {
        tata[radacina_b] = radacina_a;
        nr[radacina_a] += nr[radacina_b];
    }
    else
    {
        tata[radacina_a] = radacina_b;
        nr[radacina_b] += nr[radacina_a];
    }
}

void testcase()
{
    int n, m;
    fin >> n >> m;
    vector<muchie> muchii;
    int cost_total = 0;

    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        fin >> u >> v >> w;
        muchii.push_back({u, v, w});
    }
    sort(muchii.begin(), muchii.end(), cmp);

    for (int i = 1; i <= n; i++)
    {
        tata[i] = i;
        nr[i] = 1;
    }
    int pasi = 0;
    int i = 0;
    while (pasi < n - 1 && i < m)
    {
        int u = muchii[i].stanga;
        int v = muchii[i].dreapta;
        int w = muchii[i].cost;
        if (Find(u) != Find(v))
        {
            cost_total += w;
            Union(u, v);
            pasi++;
            arbore.push_back({u, v});
            // fout << u << " " << v << "\n";
        }
        i++;
    }
    fout << cost_total << "\n";
    fout << arbore.size() << "\n";
    for (auto muchie : arbore)
        fout << muchie.first << " " << muchie.second << "\n";
}

int main()
{
    int t = 1;
    // fin >> t;
    while (t--)
        testcase();
    return 0;
}