#include <fstream>
#include <vector>
#include <algorithm>
#define NMax 200001
using namespace std;

struct muchie   {
                    int x, y, cost;
                };

vector<muchie> muchii, sol;
muchie aux;
int N, M, v[NMax], i, j, cost_total;
vector<int> vecini[NMax];

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

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

    fin >> N >> M;
    for(i = 1 ; i <= M ; ++i)
    {
        fin >> aux.x >> aux.y >> aux.cost;
        muchii.push_back(aux);
    }
    sort(muchii.begin(), muchii.end(), cmp);

    for(i = 1 ; i <= N ; ++i)
        v[i] = i;

    for(vector<muchie>::iterator it = muchii.begin() ; (it != muchii.end()) && (sol.size() < N) ; ++it)
    {
        i = it->x;
        j = it->y;

        if(v[i] != v[j])
        {
            i = v[i];
            j = v[j];
            for(vector<int>::iterator ite = vecini[j].begin() ; ite != vecini[j].end() ; ++ite)
            {
                v[*ite] = i;
                vecini[i].push_back(*ite);
            }
            vecini[j].~vector();
            v[j] = i;
            vecini[i].push_back(j);
            sol.push_back(*it);
            cost_total += it->cost;
        }
    }

    fout << cost_total << '\n';
    fout << sol.size() << '\n';
    for(vector<muchie>::iterator it = sol.begin() ; it != sol.end() ; ++it)
        fout << it->x << ' ' << it->y << '\n';

    fin.close();
    fout.close();
    return 0;
}