#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<pair<int, pair<int, int> > >m;
vector<pair<int, int> >n;
vector<pair<int, int> >::iterator itn;
int t[200002], r[200002];
int N, M;
int i, x, y, c, j;
bool notFound;
int cost;
int gaseste(int e)
{
    if(t[e])
    {
        e = gaseste(t[e]);
    }
    return e;
}
void uneste(int u, int v)
{
    u = gaseste(u);
    v = gaseste(v);
    if(r[u] < r[v])
    {
        t[u] = v;
    }
    else if(r[u] > r[v])
    {
        t[v] = u;
    }
    else
    {
        ++r[u];
        t[v] = u;
    }
}
bool verifica(int u, int v)
{
    if(gaseste(u) == gaseste(v))
    {
        return true;
    }
    else
    {
        return false;
    }
}
int main()
{
    fin>>N>>M;
    for(i = 0; i < M; ++i)
    {
        fin>>x;
        fin>>y;
        fin>>c;
        m.push_back(make_pair(c, make_pair(x, y)));
    }
    sort(m.begin(), m.end(), less<pair<int, pair<int, int> > >() );
    for(i = 0; i < N - 1; ++i)
    {
        notFound = true;
        for(j = 0; notFound; ++j)
        {
            if(m[j].first != 1001)
            {
                notFound = verifica(m[j].second.first, m[j].second.second);
            }
        }
        --j;
        n.push_back(make_pair(m[j].second.first, m[j].second.second));
        cost += m[j].first;
        uneste(m[j].second.first, m[j].second.second);
        m[j].first = 1001;
    }
    fout<<cost<<'\n';
    fout<<(N - 1);
    for(itn = n.begin(); itn < n.end(); ++itn)
    {
        fout<<'\n'<<itn->first<<" "<<itn->second;
    }
    return 0;
}