#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream gout("apm.out");

class Graf
{
    private:
    int noduri;
    vector< pair< pair <int, int>, int> > lista_muchii;
    vector< int > reprez;
    vector< int > dim;
    vector< pair<int, int> > rez;
    int muchii;
public:
    Graf ();
    Graf (int noduri);
    void citire_graf(int m);
    void APM();
    void unite(int x, int y);
    int Find(int x);

};

Graf :: Graf ()
{
    vector< pair< pair <int, int>, int> > aux;
    noduri = 0;
    lista_muchii =  aux;

}
Graf :: Graf (int n)
{
    noduri = n;
}
void Graf :: citire_graf (int muchii)
{
    int x,y,c;
    for ( int i = 1; i <= muchii; i++ )
    {
        cin >> x >> y >>c;
        lista_muchii.push_back(make_pair(make_pair(x,y),c));
    }
}
int Graf :: Find(int x) {
    while (x != reprez[x]) {
        x = reprez[x];
}

return x;
}


bool SorteazaDupaCost(const pair< pair<int,int>, int> &a,
                    const pair< pair<int,int>, int> &b)
{
    return (a.second < b.second);
}

void Graf:: unite(int nod1,int nod2)
{
    nod1 = Find(nod1);
    nod2 = Find(nod2);

    if (dim[nod1] <= dim[nod2])
    {
    reprez[nod1] = nod2;
    dim[nod2] += dim[nod1];
    muchii++;
    }
    else
    {
    reprez[nod2] = nod1;
    dim[nod1] += dim[nod2];
    muchii++;
    }

}
void Graf :: APM()
{   int suma_cost = 0;
    muchii = 0;
    reprez.resize(noduri+1);
    dim.resize(noduri+1);
    for(int i = 1; i <= noduri; i++)
        {reprez[i] = i;
        dim[i] = 1;
        }
    sort(lista_muchii.begin(), lista_muchii.end(),SorteazaDupaCost);
    for (int i = 0; i < lista_muchii.size(); i++)
        if(reprez[lista_muchii[i].first.first] != reprez[lista_muchii[i].first.second])
           {
               unite(lista_muchii[i].first.first, lista_muchii[i].first.second);
               rez.push_back(make_pair(lista_muchii[i].first.second, lista_muchii[i].first.first));
            suma_cost+= lista_muchii[i].second;
           }
    cout<<suma_cost<<'\n';
    cout<<muchii<<'\n';
    for(int i = 0; i< muchii; i++)
        cout<<rez[i].first << ' ' << rez[i].second<<'\n';

}

int main()
{
    int n,m;
    cin>>n>>m;
    Graf g(n);
    g.citire_graf(m);
    g.APM();
    return 0;
}