#include <bits/stdc++.h>

using namespace std;

struct muchie
{
    int cost;
    int sursa;
    int dest;
};

set<muchie> graf;
vector<int> parinte;
vector<pair<int, int>> sol;

bool operator < (muchie a, muchie b)
{
    if (a.cost == b.cost && a.sursa == b.sursa)
    {
        return a.dest < b.dest;
    }
    else
    {
        if (a.cost == b.cost)
        {
            return a.sursa < b.sursa;
        }
        else
        {
            return a.cost < b.cost;
        }
    }
}

int cauta_radacina(int x)
{
    if (x == parinte[x])
    {
        return x;
    }
    else
    {
        return parinte[x] = cauta_radacina(parinte[x]);
    }
}
void uniune(int x, int y)
{
    int frunza, radacina;
    frunza=cauta_radacina(x);
    radacina=cauta_radacina(y);
    parinte[frunza]=radacina;
}

void kruskal(int n, int m)
{
    int k, x, y, total_cost;
    total_cost = k = 0;
    auto it = graf.begin();
    while (k < n - 1)
    {
        if (cauta_radacina(it->sursa) != cauta_radacina(it->dest))
        {
            k++;
            total_cost = total_cost + it->cost;
            sol.push_back(make_pair(it->sursa, it->dest));

            uniune(parinte[it->dest], parinte[it->sursa]);
        }
        it++;
    }
    fout << total_cost << "\n";
}

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int noduri, muchii, x, y, c;
    fin>>noduri>>muchii;
    for (int i=0; i<=noduri; ++i)
    {
        parinte.push_back(i);
    }
    for (int i=0; i<muchii; ++i)
    {
        fin>>x>>y>>c;
        graf.insert(muchie{c,x,y});
    }
    kruskal(noduri,muchii);
    fout<<sol.size()<<"\n";
    for (auto it : sol)
    {
        fout<<it.first<<" "<<it.second<<"\n";
    }
    return 0;
}