#include <fstream>
#include <set>
#define N 400003
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,i,j,k,cost,total,h,rad,x,y,e;
int u[N],v[N],c[N],viz[N],ta[N],muc[N];
set<pair<int,int> > s;
set<pair<int,int> >::iterator it;

int main()
{
    f >> n >> m;
    for(i = 1; i <= m; i++)
    {
        f >> u[i] >> v[i] >> c[i];
        s.insert({c[i],i});
    }
    k = 0;
    while(k < n-1)
    {
        it = s.begin();
        cost = (*it).first;
        j = (*it).second;
        s.erase(it);
        if((viz[u[j]]==1)and(viz[v[j]]==1))
        {
            h = u[j];
            while(h!=0)
            {
                x = h;
                h = ta[h];
            }
            e = v[j];
            while(e!=0)
            {
                y = e;
                e = ta[e];
            }
            if(x!=y)
            {
                total += cost;
                k++; muc[k] = j;
                h = v[j];
                while(h!=0)
                {
                    y = ta[h];
                    ta[h] = x;
                    h = y;
                }
            }
        }
        else
        if((viz[u[j]]==0)and(viz[v[j]]==0))
        {
            ta[v[j]] = u[j];
            total += cost;
            viz[u[j]] = 1;
            viz[v[j]] = 1;
            k++; muc[k] = j;
        }
        else
        if(viz[u[j]]==0)
        {
            total += cost;
            viz[u[j]] = 1;
            k++; muc[k] = j;
            h = v[j];
            while(h!=0)
            {
                rad = h;
                h = ta[h];
            }
            h = u[j];
            while(h!=0)
            {
                x = ta[h];
                ta[h] = rad;
                h = x;
            }
        }
        else
        if(viz[v[j]]==0)
        {
            total += cost;
            viz[v[j]] = 1;
            k++; muc[k] = j;
            h = u[j];
            while(h!=0)
            {
                rad = h;
                h = ta[h];
            }
            h = v[j];
            while(h!=0)
            {
                x = ta[h];
                ta[h] = rad;
                h = x;
            }
        }
    }
    g << total << "\n";
    g << k << "\n";
    for(i = 1; i <= k; i++)
        g << u[muc[i]] << " " << v[muc[i]] << "\n";
    return 0;
}