#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

int n,m,q,nrM,v[101];
long long CostTotal;

struct muchie
{
    int nod1,nod2,cost;
} M[5000],M2[5000];

bool Sortare(muchie a, muchie b)
{
    return a.cost<b.cost;
}

int Arbore(int Nod)
{
    if (Nod!=v[Nod])
        return Arbore(v[Nod]);
}

void Unire(int Nod1, int Nod2)
{
    v[Nod1]=Nod2;
}

int main(void)
{
    cin>>n>>m;
    for (int i=1; i<=m; ++i)
        cin>>M[i].nod1>>M[i].nod2>>M[i].cost;
    sort (M+1,M+m+1,Sortare);
    for (int i=1; i<=n; ++i)
        v[i]=i;
    for (int i=1; i<=m; ++i)
    {
        int a=Arbore(M[i].nod1);
        int b=Arbore(M[i].nod2);
        if (a!=b)
        {
            Unire(a,b);
            CostTotal+=M[i].cost;
            M2[++q].nod1=M[i].nod1;
            M2[q].nod2=M[i].nod2;
            nrM++;
        }
    }
    cout<<CostTotal<<'\n'<<nrM<<'\n';
    for (int i=1; i<=q; ++i)
        cout<<M2[i].nod1<<" "<<M2[i].nod2<<'\n';
}