#include <iostream>
#include <fstream>
#define MAX 200001
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,muchii,tata[MAX],rang[MAX],sum,muc[MAX],nr;
struct graf{
    int nod1,nod2,cost;
}m[MAX],aux;

bool unire(int x,int y);
int findT(int x);

int main()
{
    in>>n>>muchii;
    for (int i=1;i<=muchii;i++)
    {
        in>>m[i].nod1>>m[i].nod2>>m[i].cost;
        if (m[i].cost < m[i-1].cost)
            for (int j=i-1;j>0;j--)
            {
                if (m[j+1].cost < m[j].cost)
                {
                    aux = m[j+1];
                    m[j+1] = m[j];
                    m[j] = aux;
                }
            }
    }
    for (int i=1;i<=n;i++) tata[i] = i;
    for (int i=1;i<=muchii;i++)
    {
        if (nr<n-1)
        {
            if (unire(m[i].nod1,m[i].nod2))
            {
                nr++;
                muc[nr]=i;
                sum+=m[i].cost;
            }
        }
        else break;
    }
    out<<sum<<endl<<nr<<endl;
    for (int i=1;i<=nr;i++)
    {
        out<<m[muc[i]].nod1<<" "<<m[muc[i]].nod2<<endl;
    }
    return 0;
}

int findT(int x)
{
    if (x==tata[x]) return x;
    else
    {
        int tati=findT(tata[x]);
        tata[x]=tati;
        return tati;
    }
}

bool unire(int x,int y)
{
    int tataX = findT(x);
    int tataY = findT(y);

    if (tataX != tataY)
    {
        if (rang[tataX] > rang[tataY])
        {
            tata[tataY] = tataX;
        }
        else
        {
            if (rang[tataX] < rang[tataY])
            {
                tata[tataX] = tataY;
            }
            else
            {
                tata[tataX] = tataY;
                rang[tataY]++;
            }
        }
        return true;
    }
    return false;
}