#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 500002;
int tati[NMAX], inaltime[NMAX];
vector <pair<int, pair<int, int>>> muchii;
vector <pair<int, pair<int, int>>> muchii_finale;
int n, m, cost_final;

int radacina(int nod)
{
    int rad = nod;
    while(rad != tati[rad])
    {
        rad = tati[rad];
    }

    while(nod != rad)
    {
        int aux = tati[nod];
        tati[nod] = rad;
        nod = aux;
    }
    return rad;
}

void unite(int x, int y)
{
    x = radacina(x);
    y = radacina(y);

    if(inaltime[x] > inaltime[y])
        tati[y] = x;
    else if(inaltime[x] < inaltime[y])
        tati[x]= y;
    else{
        tati[x] = y;
        inaltime[y]++;
    }
}

int main()
{
    fin >> n >> m;
    for(int i=1; i<=n; ++i)
    {
        tati[i] = i;
        inaltime[i] = 1;
    }

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

    sort(muchii.begin(), muchii.end());

    for(auto i : muchii)
    {
        int nod1 = i.second.first;
        int nod2 = i.second.second;
        int cost = i.first;

        if(radacina(nod1) == radacina(nod2))
            continue;

        unite(nod1, nod2);
        muchii_finale.push_back(make_pair(cost, make_pair(nod1, nod2)));
        cost_final += cost;
    }

    fout << cost_final << "\n";
    fout << muchii_finale.size() << "\n";

    for(auto i : muchii_finale)
        fout << i.second.first << " " << i.second.second << "\n";
    return 0;
}